Sudoku solver
#include
using namespace std;
constint BOARD_SIZE = 9;
boolcheck_solution(int board[][BOARD_SIZE]){
}
bool solve(int board[][BOARD_SIZE], int i, int j){
}
boolsolve_sudoku(int board[][BOARD_SIZE]){
return solve(board, 0, 0);
}
//fill the int array given a digits string describing the puzzle board
voidfill_board(int board[][BOARD_SIZE], const char s[])
{
intlen = BOARD_SIZE * BOARD_SIZE;
for(int i = 0; i
board[i / BOARD_SIZE][i % BOARD_SIZE] = (int)(s[i] – ‘0’);
}
voidprint_board(int board[][BOARD_SIZE])
{
cout<< “Sudoku board” <
for(int i = 0; i < BOARD_SIZE; ++i)
{
for(int j = 0; j < BOARD_SIZE; ++j)
cout<< (j ? ” ” : “”) << board[i][j];
cout<
}
}
void go_task1()
{
constintn_cases = 10;
const char sample_boards[n_cases][BOARD_SIZE * BOARD_SIZE + 1] = {
“143628579572139468986754231391542786468917352725863914237481695619275843854396127”,
“123456789578139624496872153952381467641297835387564291719623548864915372235748916”,
“123456789965718423847329165632871954589634217714295638298567341351942876476183592”,
“123456789549873261867129435615798324432615978978342516296587143784931652351264897”,
“123456789549178263786239415698721534235964871417583926364892157972615348851347692”,
“534678912672196348197342567859761423426853791713924856961537284287419635345286179”,
“323456789965718423847329165632871954589634217714295638298567351351942876476183592”,
“123456789457918362689372545932164857768529431214783926895237614276848593341695278”,
“723456789867912345459738612534187926782694153691325874915273468276849531348561297”,
“123456789698317254457829136386741592579632418641598673964173825735284961812965347”};
cout<< “Please enter the ID of test cases, input -1 to run all of cases” <
intcase_id;
cin>>case_id;
int board[BOARD_SIZE][BOARD_SIZE];//array holder for sudoku
if(case_id == -1)
{ //run all test cases if entering -1
for(case_id = 0; case_id
{
cout<< “Running test case ” <
fill_board(board, sample_boards[case_id]);
print_board(board);
if(check_solution(board))
cout<< “Valid” <
else
cout<< “Invalid” <
cout<
}
}
else if(case_id>= 0 &&case_id
{
cout<< “Running test case ” <
fill_board(board, sample_boards[case_id]);
print_board(board);
if(check_solution(board))
cout<< “Valid” <
else
cout<< “Invalid” <
cout<
}
else
cout<< “Invalid test case ID.” <
}
void go_task2()
{
constintn_cases = 16;
const char sample_boards[n_cases][BOARD_SIZE * BOARD_SIZE + 1] = {
“530070000600195000098000060800060003400803001700020006060000280000419005000080079”,
“009748000700000000020109000007000240064010590098000300000803020000000006000275900”,
“001700509573024106800501002700295018009400305652800007465080071000159004908007053”,
“625038970009200005040095302987020030150067009000019587498601053000083640016002090”,
“056090800910805702030607590000002106460951287127008000089126473001009000670040910”,
“260501300700820561305006008401369800053470100800000643174600900900157284002004006”,
“239000405000950007607314209071006502063085074004091600002500840385140926100820000”,
“356970081000600034802501700508420106100060450604150800001897045485006072003040600”,
“062403817010006003038710002040960270087030500106074089800201700050007904274650130”,
“062403817010006003038710002040960270087030500106074089800201700050007904274650130”,
“530070000600196000098000060800060003400803001700020006060000280000419005000080079”,
“923001074100098002700430190304005621097806503060304000475203010610089430000007065”,
“160000079307918256005460000014080023600043005073602901700300814081020307406871000”,
“806503497504280600090400200081760005005090780067035140700901500059300802402650970”,
“030652090592870061070000520000090200814200009920134786000046005149085002056700948”,
“823579000059401720700620500076102008200008007130790452080000200007214835540037010”};
cout<< “Please enter the ID of test cases, input -1 to run all of cases” <
intcase_id;
cin>>case_id;
int board[BOARD_SIZE][BOARD_SIZE];//array holder for sudoku
if(case_id == -1)
{ //run all test cases if entering -1
for(case_id = 0; case_id
{
cout<< “Running test case ” <
fill_board(board, sample_boards[case_id]);
print_board(board);
if(solve_sudoku (board))
{
cout<< “Solution found!” <
print_board(board);
}
else
cout<< “No solution exists!” <
cout<
}
}
else if(case_id>= 0 &&case_id
{
cout<< “Running test case ” <
fill_board(board, sample_boards[case_id]);
print_board(board);
if(solve_sudoku (board))
{
cout<< “Solution found!” <
print_board(board);
}
else
{
cout<< “No solution exists!” <
}
cout<
}
else
cout<< “Invalid test case ID.” <
}
int main()
{
cout<< “***************************************************” <
cout<< “Sudoku Cracker” <
cout<< “***************************************************” <
while(true)
{
inttask_id;
cout<< “Please select task” <
cout<< “1: Sudoku Validator” <
cout<< “2: Sudoku Solver” <
cout<< “Enter 0 to exit” <
cin>>task_id;
if(task_id == 1)
go_task1();
else if(task_id == 2)
go_task2();
else if(task_id == 0)
break;
else
cout<< “Invalid input! Please re-enter the task id.” <
}
return 0;
}
Solution
sudoku.cpp
#include
using namespace std;
constint BOARD_SIZE = 9;
boolcheck_group_valid(int group[BOARD_SIZE])
{
boolisValid = true;
for (int i = 1; i <= BOARD_SIZE; i++)
{ // each possible value
for (int j = 0; j < BOARD_SIZE; j++)
{ // each cell in group
if (group[j] == i)
{
break; // value found, go to next possible value
}
else if (j == BOARD_SIZE – 1)
{
isValid = false; // last cell, value still not found, group invalid
}
}
if (!isValid)
{ // skip iterations if invalid already
break;
}
}
returnisValid;
}
boolcheck_solution(int board[][BOARD_SIZE])
{
boolisGameValid = true;
// check rows
for (int i = 0; i < BOARD_SIZE; i++)
{ // each row
int group[9] = { };
for (int j = 0; j < BOARD_SIZE; j++)
{ // each col
group[j] = board[i][j];
}
if (!check_group_valid(group))
{
isGameValid = false;
break;
}
}
if (!isGameValid)
{
returnisGameValid;
}
// check cols
for (int i = 0; i < BOARD_SIZE; i++)
{ // each col
int group[9] = { };
for (int j = 0; j < BOARD_SIZE; j++)
{ // each row
group[j] = board[j][i];
}
if (!check_group_valid(group))
{
isGameValid = false;
break;
}
}
if (!isGameValid)
{
returnisGameValid;
}
// check boxes
for (int i = 0; i < 3; i++)
{ // row offset
for (int j = 0; j < 3; j++)
{ // col offset
int group[9] = { };
introwOffset = i * 3;
intcolOffset = j * 3;
for (int i = 0; i < 3; i++)
{ // each row of box
for (int j = 0; j < 3; j++)
{ // each col of box
group[j + 3 * i] = board[i + rowOffset][j + colOffset];
}
}
if (!check_group_valid(group))
{
isGameValid = false;
break;
}
}
if (!isGameValid)
{
break;
}
}
returnisGameValid;
}
boolisGuessLegal(int board[][BOARD_SIZE], int row, int col, int guess)
{
introwGroup[BOARD_SIZE] = { };
intcolGroup[BOARD_SIZE] = { };
intboxGroup[BOARD_SIZE] = { };
introwOffset = row / 3 * 3;
intcolOffset = col / 3 * 3;
for (int i = 0; i < BOARD_SIZE; i++)
{
rowGroup[i] = board
[row]
[i];
colGroup[i] = board[i][col];
}
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
boxGroup[j + 3 * i] = board[i + rowOffset][j + colOffset];
}
}
for (int i = 0; i < BOARD_SIZE; i++)
{
if (rowGroup[i] == guess)
{
return false;
}
if (colGroup[i] == guess)
{
return false;
}
if (boxGroup[i] == guess)
{
return false;
}
}
return true;
}
boolisBoardEmpty(int board[][BOARD_SIZE])
{
for (int i = 0; i < BOARD_SIZE; i++)
{
for (int j = 0; j < BOARD_SIZE; j++)
{
if (board[i][j] == 0)
{
return false;
}
}
}
return true;
}
bool solve(int board[][BOARD_SIZE], int i, int j)
{
// solved found if board not empty
if (isBoardEmpty(board))
{
return true;
}
// move to next cell if cell not empty
if (board[i][j] != 0)
{
return solve(board, i + (j + 1) / BOARD_SIZE, (j + 1) % BOARD_SIZE);
}
// iterate guesses
for (int guess = 1; guess <= BOARD_SIZE; guess++)
{
if (isGuessLegal(board, i, j, guess))
{
// assign if guess is legal
board[i][j] = guess;
// recursion
if (solve(board, i, j))
{
return true;
}
else
{
// children have no solution, try next guess
board[i][j] = 0;
}
}
}
// all guesses iterated, no solution found
return false;
}
boolsolve_sudoku(int board[][BOARD_SIZE])
{
return solve(board, 0, 0);
}
//fill the int array given a digits string describing the puzzle board
voidfill_board(int board[][BOARD_SIZE], const char s[])
{
intlen = BOARD_SIZE * BOARD_SIZE;
for (int i = 0; i
board[i / BOARD_SIZE][i % BOARD_SIZE] = (int) (s[i] – ‘0’);
}
voidprint_board(int board[][BOARD_SIZE])
{
cout<< “Sudoku board” <
for (int i = 0; i < BOARD_SIZE; ++i)
{
for (int j = 0; j < BOARD_SIZE; ++j)
cout<< (j ? ” ” : “”) << board[i][j];
cout<
}
}
void go_task1()
{
constintn_cases = 10;
const char sample_boards[n_cases][BOARD_SIZE * BOARD_SIZE + 1] = { “143628579572139468986754231391542786468917352725863914237481695619275843854396127”,
“123456789578139624496872153952381467641297835387564291719623548864915372235748916”,
“123456789965718423847329165632871954589634217714295638298567341351942876476183592”,
“123456789549873261867129435615798324432615978978342516296587143784931652351264897”,
“123456789549178263786239415698721534235964871417583926364892157972615348851347692”,
“534678912672196348197342567859761423426853791713924856961537284287419635345286179”,
“323456789965718423847329165632871954589634217714295638298567351351942876476183592”,
“123456789457918362689372545932164857768529431214783926895237614276848593341695278”,
“723456789867912345459738612534187926782694153691325874915273468276849531348561297”,
“123456789698317254457829136386741592579632418641598673964173825735284961812965347” };
cout<< “Please enter the ID of test cases, input -1 to run all of cases” <
intcase_id;
cin>>case_id;
int board[BOARD_SIZE][BOARD_SIZE]; //array holder for sudoku
if (case_id == -1)
{ //run all test cases if entering -1
for (case_id = 0; case_id
{
cout<< “Running test case ” <
fill_board(board, sample_boards[case_id]);
print_board(board);
if (check_solution(board))
cout<< “Valid” <
else
cout<< “Invalid” <
cout<
}
}
else if (case_id>= 0 &&case_id
{
cout<< “Running test case ” <
fill_board(board, sample_boards[case_id]);
print_board(board);
if (check_solution(board))
cout<< “Valid” <
else
cout<< “Invalid” <
cout<
}
else
cout<< “Invalid test case ID.” <
}
void go_task2()
{
constintn_cases = 16;
const char sample_boards[n_cases][BOARD_SIZE * BOARD_SIZE + 1] = { “530070000600195000098000060800060003400803001700020006060000280000419005000080079”,
“009748000700000000020109000007000240064010590098000300000803020000000006000275900”,
“001700509573024106800501002700295018009400305652800007465080071000159004908007053”,
“625038970009200005040095302987020030150067009000019587498601053000083640016002090”,
“056090800910805702030607590000002106460951287127008000089126473001009000670040910”,
“260501300700820561305006008401369800053470100800000643174600900900157284002004006”,
“239000405000950007607314209071006502063085074004091600002500840385140926100820000”,
“356970081000600034802501700508420106100060450604150800001897045485006072003040600”,
“062403817010006003038710002040960270087030500106074089800201700050007904274650130”,
“062403817010006003038710002040960270087030500106074089800201700050007904274650130”,
“530070000600196000098000060800060003400803001700020006060000280000419005000080079”,
“923001074100098002700430190304005621097806503060304000475203010610089430000007065”,
“160000079307918256005460000014080023600043005073602901700300814081020307406871000”,
“806503497504280600090400200081760005005090780067035140700901500059300802402650970”,
“030652090592870061070000520000090200814200009920134786000046005149085002056700948”,
“823579000059401720700620500076102008200008007130790452080000200007214835540037010” };
cout<< “Please enter the ID of test cases, input -1 to run all of cases” <
intcase_id;
cin>>case_id;
int board[BOARD_SIZE][BOARD_SIZE]; //array holder for sudoku
if (case_id == -1)
{ //run all test cases if entering -1
for (case_id = 0; case_id
{
cout<< “Running test case ” <
fill_board(board, sample_boards[case_id]);
print_board(board);
if (solve_sudoku(board))
{
cout<< “Solution found!” <
print_board(board);
}
else
cout<< “No solution exists!” <
cout<
}
}
else if (case_id>= 0 &&case_id
{
cout<< “Running test case ” <
fill_board(board, sample_boards[case_id]);
print_board(board);
if (solve_sudoku(board))
{
cout<< “Solution found!” <
print_board(board);
}
else
{
cout<< “No solution exists!” <
}
cout<
}
else
cout<< “Invalid test case ID.” <
}
int main()
{
cout<< “***************************************************” <
cout<< “Sudoku Cracker” <
cout<< “***************************************************” <
while (true)
{
inttask_id;
cout<< “Please select task” <
cout<< “1: Sudoku Validator” <
cout<< “2: Sudoku Solver” <
cout<< “Enter 0 to exit” <
cin>>task_id;
if (task_id == 1)
go_task1();
else if (task_id == 2)
go_task2();
else if (task_id == 0)
break;
else
cout<< “Invalid input! Please re-enter the task id.” <
}
return 0;
}