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';
}
}
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...