1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150
|
#include <iostream>
using namespace std;
void readAPuzzle (int grid[][9]);
bool search(int grid [][9]);
int getFreeCellList (const int grid [][9], int freeCellList[][2]);
void printGrid(const int grid[][9]);
bool isValid(int i, int j, const int grid [][9]);
bool isValid (const int grid[][9]);
int main()
{
//Read a Sodoku puzzle
int grid[9][9];
readAPuzzle(grid);
if (!isValid(grid))
cout << "Invalid input" << endl;
else if (search(grid))
{
cout << "The solution is found:" << endl;
printGrid(grid);
}
else
cout << "No solution" << endl;
system ("pause");
return 0;
}
/** Read a Sodoku puzzle from the keyboard */
void readAPuzzle (int grid[][9])
{
// Creat a Scanner
cout << "Enter a Sudoku puzzle: \n(Remember to put a space inbetween each of the numbers of your sudoku puzzle.)" << endl;
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
cin >> grid[i][j];
}
/** Obtain a list of free cells from the puzzle */
int getFreeCellList(const int grid[][9], int freeCellList[][2])
{
//81 is the maximum number of free cells
int numberOfFreeCells = 0;
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (grid[i][j] == 0)
{
freeCellList[numberOfFreeCells][0] = i;
freeCellList[numberOfFreeCells][1] = j;
numberOfFreeCells++;
}
return numberOfFreeCells;
}
/** Display the values in the grid */
void printGrid(const int grid[][9])
{
for (int i = 0; i < 9; i ++)
{
for (int j = 0; j < 9; j++)
cout << grid[i][j] << " ";
cout << endl;
}
}
/** Search for a solution */
bool search (int grid[][9])
{
int freeCellList[81][2]; // Declare freeCellList
int numberOfFreeCells = getFreeCellList(grid, freeCellList);
if (numberOfFreeCells == 0)
return true; // No free cells
int k = 0; // Start from the first free cell
while (true)
{
int i = freeCellList[k][0];
int j = freeCellList[k][1];
if (grid[i][j] == 0)
grid[i][j] = 1; // Fill the free cell with number 1
if (isValid(i, j, grid))
{
if (k+1 == numberOfFreeCells)
{ // No more free cells
return true; // a solution is found
}
else
{ // Move to the next free cell
k++;
}
}
else if (grid[i][j] < 9)
{
//Fill the free cell with the next possible value
grid[i][j] = grid[i][j] + 1;
}
else
{ // grid[i][j] is 9, backtrack
while (grid[i][j] == 0)
{
return false; //No possble value
}
grid[i][j] = grid[i][j] + 1;
}
}
return true; // A solution is found
}
/** Check whether grid[i][j] is valid in the grid */
bool isValid(int i, int j, const int grid[][9])
{
// Check whether grid[i][j] is valid at the i's row
for (int column = 0; column < 9; column++)
if (column != j && grid [i][column] == grid [i][j])
return false;
// Check whether grid[i][j] is valid at the j's column
for (int row = 0; row < 9; row++)
if (row != i && grid[row][j] == grid[i][j])
return false;
//check whether grid[i][j] is valid in the 3-by-3 box
for (int row = (i / 3) * 3; row < (i /3) * 3 + 3; row++)
for (int col = (j / 3) * 3; col <(j / 3) * 3 + 3; col++)
if (row != i && col != j && grid[row][col] == grid[i][j])
return true; // the current value at grid[i][j] is valid
}
/** Check whether the vided cells are valid in the grid */
bool isValid(const int grid[][9])
{
for (int i = 0; i < 9; i++)
for (int j=0; j < 9; j++)
if (grid[i][j] < 0 || grid [i][j] > 9 || (grid[i][j] != 0 && !isValid(i, j, grid)))
return false;
return true; // The fixed cells are valid
}
|