Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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