# Sudoku solver

I know… Another contest?? Well, not exactly. This is not a real contest.
I am researching about Sudoku algorithms to generate and solve 9x9 boards.
This is not so easy as it seems. Some “hard” Sudokus can take more than 180 seconds to be solved by a computer!

So, my idea: Lets see who can create the best algorithm to solve 1000 (example) Sudokus more efficiently.
Sudoku format: 4…5.8.3…7…2…6…5.8…1…6.3.7.5…2…1.8…
Rules:
-Track how much time it takes in milliseconds to solve all the Sudokus (better in different computers).
-Track how many loops, tries and errors were needed to solve them.

Good or bad idea? I will need to make one anyways for my next game. Would be fun some competition. ;D

Did this on Hackerrank a while ago, used a nifty little recursive depth-first search as it is a code-length challenge. I had to remove some heuristics for the challenge, but it still ran real fast. I’m curious to see what people do.

This is roughly the algorithm I started from: http://www.sysexpand.com/?path=exercises/sudoku-solver

Will post code after I make it comprehensible. (if that’s possible :\ )

I wrote a solver which calculates tough sudoku’s in about 1/3rd of a second. It doesn’t have any techniques or fancy strategies: for solving 1 puzzle it’s fast enough. It just fills in the next empty cell, unless it can’t, then it tries to increase the value of the previous cell, unless it can’t, etc etc. Worst case would be that it arrives at the last cells and has to backtrack all the way back to the first cells, repeatedly.

``````
import java.util.Arrays;

public class Sudoku
{
public static void main(String[] args)
{
int[] grid = {//
0, 0, 3, 6, 0, 0, 8, 0, 0,//
0, 0, 9, 0, 0, 0, 0, 0, 3,//
0, 7, 0, 0, 0, 0, 0, 2, 0,//
0, 0, 1, 0, 0, 0, 7, 0, 4,//
0, 0, 7, 0, 0, 2, 0, 0, 0,//
9, 5, 0, 0, 0, 0, 0, 6, 0,//
0, 0, 0, 0, 0, 1, 2, 0, 0,//
8, 0, 0, 3, 0, 0, 6, 0, 0,//
0, 0, 0, 7, 4, 0, 9, 0, 0 };
print(grid);

int[] work = grid.clone();
if(solve(work, 0))
print(work);

for(int i = 0; i < 4; i++)
{
long t1 = System.currentTimeMillis();
solve(grid.clone(), 0);
long t2 = System.currentTimeMillis();
System.out.println("solving took: " + (t2 - t1) + "ms");
}
}

public static void print(int[] grid)
{
for(int i = 0; i < 81; i += 9)
System.out.println(Arrays.toString(Arrays.copyOfRange(grid, i, i + 9)));
System.out.println();
}

public static boolean solve(int[] grid, int cell)
{
while (cell < 81 && grid[cell] > 0)
cell++;
if(cell == 81)
return true;

for(int i = 1; i <= 9; i++)
{
grid[cell] = i;
+			if(isColumnValid(grid, cell % 9))
+				if(isRowValid(grid, cell / 9))
+					if(isBlockValid(grid, cell % 3 * 3, cell / 9 % 3 * 3))
if(isValid(grid) && solve(grid, cell + 1))
return true;
}
grid[cell] = 0;
return false;
}

private static final int[] freqs = new int[10];

public static boolean isValid(int[] grid)
{
for(int i = 0; i < 9; i++)
{
if(!isRowValid(grid, i))
return false;
if(!isColumnValid(grid, i))
return false;
if(!isBlockValid(grid, i % 3 * 3, i / 3 * 3))
return false;
}
return true;
}

public static boolean isRowValid(int[] grid, int row)
{
Arrays.fill(freqs, 0);

for(int i = 0; i < 9; i++)
{
int cell = grid[row * 9 + i];
if(cell > 0 && ++freqs[cell] > 1)
return false;
}
return true;
}

public static boolean isColumnValid(int[] grid, int col)
{
Arrays.fill(freqs, 0);

for(int i = 0; i < 9; i++)
{
int cell = grid[i * 9 + col];
if(cell > 0 && ++freqs[cell] > 1)
return false;
}
return true;
}

public static boolean isBlockValid(int[] grid, int x, int y)
{
Arrays.fill(freqs, 0);

for(int i = 0; i < 9; i++)
{
int cell = grid[(y + i / 3) * 9 + (x + i % 3)];
if(cell > 0 && ++freqs[cell] > 1)
return false;
}
return true;
}
}

``````
``````
[0, 0, 3, 6, 0, 0, 8, 0, 0]
[0, 0, 9, 0, 0, 0, 0, 0, 3]
[0, 7, 0, 0, 0, 0, 0, 2, 0]
[0, 0, 1, 0, 0, 0, 7, 0, 4]
[0, 0, 7, 0, 0, 2, 0, 0, 0]
[9, 5, 0, 0, 0, 0, 0, 6, 0]
[0, 0, 0, 0, 0, 1, 2, 0, 0]
[8, 0, 0, 3, 0, 0, 6, 0, 0]
[0, 0, 0, 7, 4, 0, 9, 0, 0]

[2, 4, 3, 6, 5, 7, 8, 9, 1]
[6, 8, 9, 2, 1, 4, 5, 7, 3]
[1, 7, 5, 9, 3, 8, 4, 2, 6]
[3, 2, 1, 5, 6, 9, 7, 8, 4]
[4, 6, 7, 1, 8, 2, 3, 5, 9]
[9, 5, 8, 4, 7, 3, 1, 6, 2]
[7, 3, 6, 8, 9, 1, 2, 4, 5]
[8, 9, 4, 3, 2, 5, 6, 1, 7]
[5, 1, 2, 7, 4, 6, 9, 3, 8]

-solving took: 1027ms
-solving took: 1026ms
-solving took: 1023ms
-solving took: 1027ms
+solving took: 390ms
+solving took: 389ms
+solving took: 387ms
+solving took: 387ms

``````

World’s hardest sudoku for mere mortals:

http://i.telegraph.co.uk/multimedia/archive/02260/Untitled-1_2260717b.jpg

``````
[8, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 3, 6, 0, 0, 0, 0, 0]
[0, 7, 0, 0, 9, 0, 2, 0, 0]
[0, 5, 0, 0, 0, 7, 0, 0, 0]
[0, 0, 0, 0, 4, 5, 7, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 3, 0]
[0, 0, 1, 0, 0, 0, 0, 6, 8]
[0, 0, 8, 5, 0, 0, 0, 1, 0]
[0, 9, 0, 0, 0, 0, 4, 0, 0]

[8, 1, 2, 7, 5, 3, 6, 4, 9]
[9, 4, 3, 6, 8, 2, 1, 7, 5]
[6, 7, 5, 4, 9, 1, 2, 8, 3]
[1, 5, 4, 2, 3, 7, 8, 9, 6]
[3, 6, 9, 8, 4, 5, 7, 2, 1]
[2, 8, 7, 1, 6, 9, 5, 3, 4]
[5, 2, 1, 9, 7, 4, 3, 6, 8]
[4, 3, 8, 5, 2, 6, 9, 1, 7]
[7, 9, 6, 3, 1, 8, 4, 5, 2]

solving took: 75ms
solving took: 76ms
solving took: 76ms
solving took: 75ms

``````

I still need to wrote mine. First I am trying to generate a Sudoku, but this is hard because I need a smart way to create difficulty (easy, normal, hard, hardest) and every generated boards can only have 1 final solution.

Having a solver is a key piece of creating a generator. You can basically fill a grid with random values (checking isValid after each insertion) and stop after you filled the grid for a certain percentage and clone it. Then you solve it, and if there is a solution, you start solving the sparse grid in randomized order (instead of sequentially) using permutations of [0,1,2,3,…]. After solving it a dozen times and getting the same answer, the chance of there being multiple solutions rapidly approaches zero.

As for how hard it is to solve… I’m not sure I have a solution for that yet.

Alright, here’s mine, expanded a bit from the HR challenge, solving the same grid as Riven’s:

``````class Sudoku {
static int[] grid;

static boolean solve() {
for (int cell = 0, number, i; cell < 81; cell++)
if (grid[cell] < 1) {
check: for (number = 0; number++ < 9;) {
for (i = 0; i < 9; i++)
if (grid[cell / 9 * 9 + i] == number | grid[cell % 9 + 9 * i] == number | grid[(cell - cell % 3) % 9 + cell / 27 * 27 + i % 3 + i / 3 * 9] == number) continue check;
grid[cell] = number;
if (solve()) return true;
grid[cell] = 0;
}
return false;
}
return true;
}

public static void main(String[] args) {
grid = new int[] {//
0, 0, 3, 6, 0, 0, 8, 0, 0,//
0, 0, 9, 0, 0, 0, 0, 0, 3,//
0, 7, 0, 0, 0, 0, 0, 2, 0,//
0, 0, 1, 0, 0, 0, 7, 0, 4,//
0, 0, 7, 0, 0, 2, 0, 0, 0,//
9, 5, 0, 0, 0, 0, 0, 6, 0,//
0, 0, 0, 0, 0, 1, 2, 0, 0,//
8, 0, 0, 3, 0, 0, 6, 0, 0,//
0, 0, 0, 7, 4, 0, 9, 0, 0 };
for (int j = 0; j < 81;)
System.out.print(grid[j++] + (j % 9 == 0 ? "\n" : " "));
System.out.println();
long time = System.nanoTime();
solve();
time = System.nanoTime() - time;
for (int j = 0; j < 81;)
System.out.print(grid[j++] + (j % 9 == 0 ? "\n" : " "));
System.out.println("Time: " + time / 1000000 + " ms");
}
}
``````

[quote]0 0 3 6 0 0 8 0 0
0 0 9 0 0 0 0 0 3
0 7 0 0 0 0 0 2 0
0 0 1 0 0 0 7 0 4
0 0 7 0 0 2 0 0 0
9 5 0 0 0 0 0 6 0
0 0 0 0 0 1 2 0 0
8 0 0 3 0 0 6 0 0
0 0 0 7 4 0 9 0 0

2 4 3 6 5 7 8 9 1
6 8 9 2 1 4 5 7 3
1 7 5 9 3 8 4 2 6
3 2 1 5 6 9 7 8 4
4 6 7 1 8 2 3 5 9
9 5 8 4 7 3 1 6 2
7 3 6 8 9 1 2 4 5
8 9 4 3 2 5 6 1 7
5 1 2 7 4 6 9 3 8
Time: 91 ms
[/quote]
Same basic approach, although it lacks a heuristic that would speed it up a lot, instead of starting the recursive search on the first blank square, start on the cell with the most constraints. Still quite effective though.

@Riven I need a fast sudoku generator and this is not so simple. The last digits most of the times will not fit and it needs to try over and over again. When the board is full, I need to remove some digits and check every time for all the possible combinations. If more than one combination is possible, I need to redo the last digit and start again. At least 17 default digits are needed to have a Sudoku than can be solved. To test difficulty, I need to check how “humans” can reveal the numbers. In this site they explain the rules to solve the board. For the Easy levels I could leave easy hints and for the hardest levels don’t.
But this is hard to do. I guess I am over thinking again (this happens a lot with me). Maybe I will just grab some Sudoku generator and create some predefined levels for my game. Then, I just need to create one Sudoku solver algorithm to check for wrong digits.

Heh, looks like this is the same same as http://projecteuler.net/problem=96 For which I never finished my own solver, because I wanted to implement all sorts of clever methods.

Maybe today is the day I get my act together and finish it.

[quote=“Riven,post:5,topic:47428”]
My approach to that is to solve it using human-like reasoning rules (this is only value which isn’t prohibited from being in this cell, this is the only cell in this group of 9 which isn’t prohibited from having this value, etc), assigning a difficulty weight to each one, and then calculating the minimal total weight to solve the grid.

A better way of calculating the difficulty would be to define it inductively over the entire graph of partial solutions whose edges are defined by these reasoning rules, using something like a harmonic mean to take into account that it’s easier to solve if the number of possible next steps is consistently high, but that becomes very computationally expensive.