Sudoku solution generator algorithm

I'm making a sudoku game using the win32 api atm, but for some reason, I can't seem to get my solution generator method to work as it should.

The way that I'm doing it, is like this (it's not the most efficient way of doing it, but atm, thats not my main concern):
It cycles through the smaller 3x3 grids one by one, randomly selecting an x and y coordinate, and provided that neither the column or the row it selects already has that number, and the square is empty, it places the number there. It first cycles through and places all the 1s, then all the 2s etc. The problem is, I'm still ending up with problems. This is my source code so far (all variables init to zero)...

Code:

for(idx0=1; idx0<NUM_BUTTONS; idx0++) { for(idx1=0; idx1<(BUTTON_NUM_Y/3); idx1++) { for(idx2=0; idx2<(BUTTON_NUM_X/3); idx2++) { /* Generate x and y values, making sure not to have two in the same row or column */ do { num1 = rand()%3 + (3*idx2); num2 = rand()%3 + (3*idx1); } while( (this->solution[num1][num2] != 0)&&((temp_x[num1] == 1)||(temp_y[num2] == 1)) ); /* Change the index for future numbers */ temp_x[num1] = 1; temp_y[num2] = 1; /* If it gets this far, it's a good value, so record it */ this->solution[num1][num2] = idx0; } } /* Reset the temporary array */ for(idx3=0; idx3<(NUM_BUTTONS - 1); idx3++) { temp_x[idx3] = 0; temp_y[idx3] = 0; } }

The temp_x and temp_y variables are used to keep track which columns and rows there are already values in. They are reset once the next number to place on the board is selected. I end up with some strange program output from this. although I can't find the bug anywhere.

I would say that your do-while loop needs || where it has && (your program will cheerfully overwrite a previously-filled square, if the temp_x/temp_y check fails).

Quote:

Originally Posted by tabstop

I would say that your do-while loop needs || where it has && (your program will cheerfully overwrite a previously-filled square, if the temp_x/temp_y check fails).

I thought that, but when I try that, it just forms an infinite loop, and doesn't knock out any numbers at all, I'm not entirely sure why, cos when I try and follow the logic through in my head, it seems to work, but as that person from Little Britain says - "Computer says no", lol.

Wait -- you weren't expecting an infinite loop? Why not? If you don't luck into building something solvable (or if you're trying to solve a given puzzle, if you don't luck into placing every single number correctly), then all you're going to do is go around and around trying to place a 1 where it can't go.

To solve something like this using brute force, you will need to have some way of undoing your so far solution when you end up in a "dead-end" - just like solving by hand, if you got something wrong in one place, you can't solve it, and you'll have to back up all the numbers you've done since you got something wrong (I usually just give up at that point, but I'm not a computer). I did solution that uses recursion to solve the problem. A Sudoku that is REALLY HARD takes about 3 seconds on my quite old PC [that's not a challenge - I'm convinced that if I spent some more time on the project, I'd get it to about half that].

--
Mats

Not an expert, but I have generated full boards by using a backtracking algorithm (try to solve each cell in order by trying numbers in order in them), and letting it solve an empty grid by randomizing the order numbers will be tried for each cell.

Quote:

A Sudoku that is REALLY HARD takes about 3 seconds on my quite old PC [that's not a challenge - I'm convinced that if I spent some more time on the project, I'd get it to about half that].

I think for brute-force algorithms there are no significant differences in difficulty (although it might help if you could, for example, eliminate a lot of single-candidate cells), but how long would something like this take?

Code:

......... ......... ......... ......... ........1 ........2 ........3 ........4 56789....

:)

As I haven't got my code here at work, I don't know how long that would take - if I get time to do it at the weekend (unlikely) I will report back - Since there are likely many different solutions to such a sparsely filled board, I guess it will actually be better.

By the way, my solution uses a sequential approach rather than random number, based on "what numbers are possible in this position". I'm not trying to fill a board to make a "new game" - that is a goal in the future, but right now it's not yet there.

--
Mats

Quote:

As I haven't got my code here at work, I don't know how long that would take - if I get time to do it at the weekend (unlikely) I will report back - Since there are likely many different solutions to such a sparsely filled board, I guess it will actually be better.

There are actually no solutions - what goes into the bottom-right corner (but how long would it take to find out?) :)

In my program that would take forever (since it would need to backtrack the whole solution and try every possible combination before giving up). Therefore it first sees if there are cells with no candidates (and another condition in which puzzles are unsolvable - I think groups that don't contain all numbers among candidates|given cells) and exits immediately.

Quote:

Originally Posted by anon

There are actually no solutions - what goes into the bottom-right corner (but how long would it take to find out?) :)

In my program that would take forever (since it would need to backtrack the whole solution and try every possible combination before giving up). Therefore it first sees if there are cells with no candidates (and another condition in which puzzles are unsolvable - I think groups that don't contain all numbers among candidates|given cells) and exits immediately.

I don't know if my code figures out that it's unsolvable - it's a good point. Again, given time, I will test it and fix as appropriate. But I don't get much time for hobby projects.

--
Mats

My program find out that there is no solution in 0.005s wall time (including reading in the file).

Solves this puzzle -
http://www.usatoday.com/news/offbeat...6-sudoku_x.htm
(Google for "hardest sudoku puzzle" :))

in 0.004s including IO. (0.005s was on a network drive)

Code:

85...24.. 72......9 ..4...... ...1.7..2 3.5...9.. .4....... ....8..7. .17...... ....36.4.

Code:

859612437 723854169 164379528 986147352 375268914 241593786 432981675 617425893 598736241

That's an interesting claim because the puzzle seemed quite straightforward to solve. Unfortunately my program does not have the option to display the difficulty rating of a given puzzle but it doesn't seem to require any techniques that would make it go beyond Medium on my system (assessing difficulty is another big question in generating sudokus, though).

Quote:

Originally Posted by cyberfish

Solves this puzzle -
http://www.usatoday.com/news/offbeat...6-sudoku_x.htm
(Google for "hardest sudoku puzzle" :))

in 0.004s including IO. (0.005s was on a network drive)

That's very impressive!

Mine reports taking 52.506ms on the one you posted, and discovers the one anon posted is unsolveable in 0.003ms. Easy ones seem to take around 0.569ms.
I haven't done anything towards guaging the level of difficulty for a human solver, nor do I make any attempt to verify that the provided board does not have multiple solutions.
So, what's your secret in solving that hard one really fast? :devil::cool:

anon: Although the one cyberfish posted is unbelieveably hard for human solvers, ALL sudoku's are easy for a reasonable backtracking computer program solver to solve.

Swarvy: Sorry I haven't written a Sudoku board generator, if that's what you are trying to do.

I wrote it a few months back for practice (and I have only been programming for a year or so...) so the code is quite unreadable. I can't seem to figure out exactly how it works from a glance :).

I think the key is to do a lot of precomputation. Things like whether a square belongs in a "group", and an array (I think I used a bitset) of squares "influenced" by setting a square (only they need to be checked when a new square is filled in). The board is also incrementally updated, containing a 2D boolean array of possible "fillers" for squares (1D array of bitsets in my case, since it allows fast checking of board legality. If a square has no possible fillers, that is, the bitset == 0, the board is illegal).

Bitsets help because they allow fast checking for 0, and also extracting the most significant or least significant bits set to 1 (bit scan forward or bit scan reverse, can even be precomputed, avoiding lots of loops). Also, popcounting (can again be precomputed) can be used to quickly determine the square with the fewest possible fillers (and try them first).

The code is attached if anyone is interested.

[edit]
oh and I think I used
__builtin_popcount()
and
__builtin_ctz()

so it will probably only work with gcc/icc.
[/edit]

Well, I have used the following code to generate a random solution. It is entirely "invented here" without much knowledge in the theory of sudoku programming and may not be too good at all.

This too uses bit-fiddling (for the purposes of the rest of the generator) and even the output is in binary, hence the log calculation to convert the output into human readable format :)

I guess lines like

Code:

int b = r - r % 3 + c / 3;

show that some things could have been precomputed.

Code:

#include <iostream> #include <algorithm> #include <ctime> #include <cmath> bool solve_recursive(unsigned full[9][9], int r, int c, unsigned candidates[9][9][9], unsigned row[9], unsigned col[9], unsigned box[9]) { ++c; if (c == 9) { ++r; c = 0; if (r == 9) return true; } if (full[r][c]) return solve_recursive(full, r, c, candidates, row, col, box); int b = r - r % 3 + c / 3; unsigned free = 511 ^ (row[r] | col[c] | box[b]); if (!free) return false; for (int i = 0; i < 9; ++i) { if (candidates[r][c][i] & free) { row[r] |= candidates[r][c][i]; col[c] |= candidates[r][c][i]; box[b] |= candidates[r][c][i]; full[r][c] = candidates[r][c][i]; if (solve_recursive(full, r, c, candidates, row, col, box)) return true; row[r] ^= candidates[r][c][i]; col[c] ^= candidates[r][c][i]; box[b] ^= candidates[r][c][i]; full[r][c] = 0; } } return false; } bool generate_random_solution(unsigned full[9][9]) { unsigned candidates[9][9][9]; unsigned row[9] = {0}, col[9] = {0}, box[9] = {0}; for (int r = 0; r < 9; ++r) { for (int c = 0; c < 9; ++c) { for (int i = 0; i < 9; ++i) { candidates[r][c][i] = 1 << i; } std::random_shuffle(candidates[r][c], candidates[r][c]+9); full[r][c] = 0; } } return solve_recursive(full, -1, 8, candidates, row, col, box); } int main() { srand(time(0)); unsigned puzzle[9][9]; generate_random_solution(puzzle); for (int i = 0; i != 9; ++i) { for (int j = 0; j != 9; ++j) { std::cout << log2(puzzle[i][j]) + 1 << ' '; } std::cout << '\n'; } }

Quote:

anon: Although the one cyberfish posted is unbelieveably hard for human solvers

It didn't seem to be hard at all - and that's without guessing as sudoku should be solved...

Quote:

Originally Posted by cyberfish

... determine the square with the fewest possible fillers (and try them first).

Ah, that's what I was missing. That brings it down to 2.380ms for that hardest board, but I'm doing the timing from within the app itself, so that doesn't include I/O.
I didn't bother precomputing influences either.

I get 0.003s if I have the whole board filled out in input file... so most of the time is spent in IO. I get the time using the "time" command in my shell (Linux machine).

But then I used -O3...

Ah oh well, I don't think it's meaningful comparing times at this magnitude :) I get significantly different times between different but identical runs, too.

I think the influences thing, the bitset stuff, and incrementally updating everything are just "linear optimizations" and don't change the complexity.

Yeah, I'm getting significanty variances between runs also, so there certainly isn't any point comparing speeds, and we're doing much the same thing anyway.
I'll post mine on my website next time I update it.

Swarvy: I'm still not sure whether you are trying to solve a sudoku, or generate a new board for a human to solve. Whichever it is, you'll need to show more code.
I can certainly understand why simply picking random numbers would not be a very good way to solve it, as the chance of the 9 numbers in one 3x3 area having duplicates is very high.

I'm trying to make a sudoku generator, its for a game. This is my solution code so far, although it doesn't work how it should.

Code:

/* solution.cpp */ #include "solution.h" void GAME_SOLUTION::GenerateSolution() { /* This method generates a solution which the user must then try and get. The way this method will work, is by going through the grid, 1 square at a time, and randomly selecting a number. It will then check in turn if there is another number either in the smaller 3x3 grid, the same row or the same column, if there is, then another number is selected until 1 fits. */ int idx1,idx2,ret=0; int num1; for(idx1=0; idx1<BUTTON_NUM; idx1++) { for(idx2=0; idx2<BUTTON_NUM; idx2++) { do { ret = 0; num1 = (rand()%BUTTON_NUM) + 1; /* Do the tests */ ret += this->TestRow(num1, idx1); ret += this->TestColumn(num1, idx2); ret += this->TestSmallGrid(num1, (int)(idx1/3), (int)(idx2/3)); /* Correct any potential errors */ ret = this->CorrectError(num1, idx2, idx1, ret); } while(ret != 0); this->SetSolution(num1, idx2, idx1); } } return; } bool GAME_SOLUTION::CorrectError(int num, int idx_x, int idx_y, int ret) { /* This tests to see if another number which has already been placed can be replaced by the one listed to be put down. */ int idx0,idx1; int ret2=0,val=0; if(ret != 0) { for(idx0=0; idx0<=idx_y; idx0++) { if(idx0 == idx_y) { for(idx1=0; idx1<idx_x; idx1++) { /* Check if the number fits */ ret2 = 0; val = this->GetSolution(idx1, idx0); ret2 += this->TestRow(val, idx_y); ret2 += this->TestColumn(val, idx_x); ret2 += this->TestSmallGrid(val, (int)(idx_x/3), (int)(idx_y/3)); ret2 += this->TestRow(num, idx0); ret2 += this->TestColumn(num, idx1); ret2 += this->TestSmallGrid(num, (int)(idx1/3), (int)(idx0/3)); if(ret2 == 0) { this->SetSolution(num, idx1, idx0); this->SetSolution(val, idx_x, idx_y); return false; } } } else { for(idx1=0; idx1<BUTTON_NUM; idx1++) { /* Check if the number fits */ ret2 = 0; val = this->GetSolution(idx1, idx0); ret2 += this->TestRow(val, idx_y); ret2 += this->TestColumn(val, idx_x); ret2 += this->TestSmallGrid(val, (int)(idx_x/3), (int)(idx_y/3)); ret2 += this->TestRow(num, idx0); ret2 += this->TestColumn(num, idx1); ret2 += this->TestSmallGrid(num, (int)(idx1/3), (int)(idx0/3)); if(ret2 == 0) { this->SetSolution(num, idx1, idx0); this->SetSolution(val, idx_x, idx_y); return false; } } } } } return false; } bool GAME_SOLUTION::TestRow(int num, int idx_y) { /* This method tests if there are two identical values in the same row */ int idx=0; for(idx=0; idx<BUTTON_NUM; idx++) { if(num == this->solution[idx][idx_y]) { return true; } } return false; } bool GAME_SOLUTION::TestColumn(int num, int idx_x) { /* This method tests if there are two identical values in the same column */ int idx=0; for(idx=0; idx<BUTTON_NUM; idx++) { if(this->solution[idx_x][idx] == num) { return true; } } return false; } bool GAME_SOLUTION::TestSmallGrid(int num, int idx1, int idx2) { int idx,idx0; for(idx=0; idx<(BUTTON_NUM/3); idx++) { for(idx0=0; idx0<(BUTTON_NUM/3); idx0++) { if(this->solution[(3*idx1) + idx0][(3*idx2) + idx] == num) { return true; } } } return false; } void GAME_SOLUTION::ClearSolution() { /* This clears a solution ready for the next game */ int idx1, idx2; for(idx1=0; idx1<BUTTON_NUM; idx1++) { for(idx2=0; idx2<BUTTON_NUM; idx2++) { this->solution[idx2][idx1] = 0; } } /* This seeds the RNG */ time(&(this->rand_num1)); srand((unsigned int)(this->rand_num1)); return; } void GAME_SOLUTION::SetSolution(int num, int idx_x, int idx_y) { /* This method just sets a solution value */ this->solution[idx_x][idx_y] = num; return; } unsigned int GAME_SOLUTION::GetSolution(int idx_x, int idx_y) { /* This returns the solution value for a given position */ /* The check for the win will be made in main.cpp, in the form of a function call to here inside a loop, checking if game_board gives the same result */ unsigned int num; num = this->solution[idx_x][idx_y]; return num; }

So, does it work?

I think I got somewhat the idea, but suppose in the first line you have

Code:

2 7 8 9 3 1 5 _

and now you get a random number and if it conflicts somewhere you see if you can swap it with something in the same line? As long as the random number is not 4 or 6 this will be a wasted effort.

I guess also that it might still create a situation where no matter what number you pick, it conflicts and cannot be swapped either to remove the conflict and the program goes into an infinite loop.

However, I notice that CorrectError always returns false?!

Okay. You should know that generating a useful board is usually harder than solving one. Published ones are specifically generated in such a way as to make them solveable by a (more-or-less average) human. Generating boards randomly will usually give you something that is pretty expert level.

I'm still thinking of starting out into writing as board generator and my current idea involves evaluating how many levels of recursion a solver would have to go into to discover that a guess was incorrect, for each human solver's move.
Still, that only helps gauge the difficulty of a board, not to actually make it easy to begin with, so it would have to repeatedly generate boards until it found an easy one.
Another way might be to simply count the number of steps my solver takes in solving it.

Just be aware that what you're trying to do might be out of your league, and if the above ideas don't pan out, then perhaps mine as well at this stage.

My puzzle generator works as follows:
1) create a random solution (code posted above)
2) pick a number of clues from the solution as opened
3) try to solve the resulting puzzle using a variety of logical methods (single candidate in a cell, single occurrence of a candidate in a group, pairs, triples etc)
4) if not successful pick a symmetric pair of additional clues - I think my criteria is a pair of cells that together have the greatest number of candidates - and repeat 3)
5) to minimize number of clues randomize the order in which clues where opened and try to solve the puzzle with logical methods removing each pair of clues in turn, if puzzle is solvable remove this clue-pair else put it back and try next (since initially about half the grid is given, most of the work is done in this step)
6) finally solve the puzzle one more time to assess difficulty (could be also done during all previous steps): note each solving technique required as well as a weighted sum of steps - for simple techniques like finding a "naked pair" add less than for a more advanced technique such as a "hidden triple". (The resulting assessment is not entirely satisfactory, though.)

Also, I discard puzzles that have more than 30 clues (unless in an ultra-beginner mode where you select the number of clues between 30 and 60 and where clues are just added as needed).

This is a bit slow, though, producing 1000 puzzles in 5 seconds (one a relatively fast computer) which is a problem because stumbling upon a sudoku that would be rated as "evil" might take generating about 30 - 100 (in worst cases about 200) puzzles - most of which are "easy" and "normal". But this is solved by having a background thread occasionally wake up, check if there are enough puzzles of each difficulty in store and make more as needed. So it may not be suitable if your aim is just to produce masses of puzzles as quickly as possible.