sudoku solver, because I'm bored
#include <iostream> | |
#include <vector> | |
int n = 0; | |
int board[9][9] = { | |
{n, 4, n, 1, n, n, n, n, 8}, | |
{n, n, 8, n, 6, n, n, n, n}, | |
{n, 1, n, 2, n, n, n, n, 9}, | |
{n, n, n, 8, n, n, n, 9, n}, | |
{2, n, 1, 9, n, 6, 8, n, 7}, | |
{n, 7, n, n, n, 2, n, n, n}, | |
{5, n, n, n, n, 7, n, 1, n}, | |
{n, n, n, n, 2, n, 5, n, n}, | |
{6, n, n, n, n, 1, n, 3, n}}; | |
int tmpcol[9]; | |
int tmpsq[9]; | |
int tmpsqloc[2]; | |
void printb(int b[9][9]) | |
{ | |
for (int i = 0; i < 9; i++) | |
{ | |
for (int j = 0; j < 9; j++) | |
std::cout << b[i][j] << " "; | |
std::cout << std::endl; | |
} | |
} | |
int in(int lower, int upper, int val) | |
{ | |
return lower <= val && val < upper; | |
} | |
int * row(int i, int b[9][9]) | |
{ | |
return b[i]; | |
} | |
int * col(int i, int b[9][9]) | |
{ | |
for (int j = 0; j < 9; j++) | |
tmpcol[j] = b[j][i]; | |
return &tmpcol[0]; | |
} | |
int * small_square(int r, int c, int b[9][9]) | |
{ | |
r *= 3; | |
c *= 3; | |
int k = 0; | |
for (int i = 0; i < 3; i++) | |
for (int j = 0; j < 3; j++) | |
{ | |
tmpsq[k] = b[i + r][j + c]; | |
k++; | |
} | |
return &tmpsq[0]; | |
} | |
int * what_square(int r, int c) | |
{ | |
if (in(0, 3, r)) | |
tmpsq[0] = 0; | |
else if (in(3, 6, r)) | |
tmpsq[0] = 1; | |
else if (in(6, 9, r)) | |
tmpsq[0] = 2; | |
if (in(0, 3, c)) | |
tmpsq[1] = 0; | |
else if (in(3, 6, c)) | |
tmpsq[1] = 1; | |
else if (in(6, 9, c)) | |
tmpsq[1] = 2; | |
return &tmpsq[0]; | |
} | |
bool check(int l[9]) | |
{ | |
int d[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0}; | |
for (int i = 0; i < 9; i++) | |
if (l[i] == 0) | |
continue; | |
else if (d[l[i] - 1] != 0) | |
return 0; | |
else | |
d[l[i] - 1] = 1; | |
return 1; | |
} | |
std::vector <int> solfinder(std::vector <int> list) | |
{ | |
int d[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0}; | |
for (unsigned i = 0; i < list.size(); i++) | |
if (list[i] == 0) | |
continue; | |
else | |
d[list[i] - 1] = 1; | |
std::vector <int> sols; | |
for (int i = 0; i < 9; i++) | |
if (d[i] != 1) | |
sols.push_back(i + 1); | |
return sols; | |
} | |
int solve(int b[9][9]) | |
{ | |
std::vector <int> rows; | |
std::vector <int> cols; | |
std::vector <int> n; | |
std::vector <std::vector <int> > d; | |
int * sq_loc; | |
for (int i = 0; i < 9; i++) | |
for (int j = 0; j < 9; j++) | |
if (b[i][j] == 0) | |
{ | |
rows.push_back(i); | |
cols.push_back(j); | |
n.push_back(-1); | |
sq_loc = what_square(i, j); | |
std::vector <int> tmp; | |
int * t1 = row(i, b); | |
int * t2 = col(j, b); | |
int * t3 = small_square(sq_loc[0], sq_loc[1], b); | |
for (int k = 0; k < 9; k++) | |
{ | |
tmp.push_back(t1[k]); | |
tmp.push_back(t2[k]); | |
tmp.push_back(t3[k]); | |
} | |
d.push_back(solfinder(tmp)); | |
} | |
int j = 0; | |
int p = 0; | |
int r = rows[0]; | |
int c = cols[0]; | |
b[r][c] = d[0][0]; | |
n[0] = 0; | |
while (1) | |
{ | |
j++; | |
if (p >= rows.size() - 1) | |
{ | |
std::cout << "Solved in " << j << " iterations:\n"; | |
printb(b); | |
return 0; | |
} | |
r = rows[p]; | |
c = cols[p]; | |
sq_loc = what_square(r, c); | |
if (!( check(row(r, b)) && | |
check(col(c, b)) && | |
check(small_square(sq_loc[0], sq_loc[1], b)) | |
)) | |
{ | |
n[p]++; | |
b[rows[p]][cols[p]] = d[p][n[p]]; | |
} | |
else | |
{ | |
p++; | |
n[p] = 0; | |
b[rows[p]][cols[p]] = d[p][n[p]]; | |
} | |
while (n[p] > d[p].size() - 1 ) | |
{ | |
n[p] = -1; | |
b[rows[p]][cols[p]] = 0; | |
p--; | |
n[p]++; | |
b[rows[p]][cols[p]] = d[p][n[p]]; | |
} | |
} | |
} | |
int main(int argc, char* argv[]) | |
{ | |
solve(board); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment