function Solve() on c++ for solving the sudoku puzzle •If A is a Sudoku object,A
ID: 3807804 • Letter: F
Question
function Solve() on c++ for solving the sudoku puzzle
•If A is a Sudoku object,A.Solve();
solves the puzzle resulting in a complete and valid grid forA.
•You can assume the input puzzle is always solvable.
Sudoku File Format:
The following is an example sudoku input file (say 0_sudoku_grid.txt).
*****329*
*865*****
*2***1***
**37*51**
9*******8
**29*83**
***4***8*
*****647*
*471*****
Overall, it’s a 9×9 grid containing numbers (between 1 and 9) and the character. It is unsolved and the’s indicate the cells that need to be filled correctly. After solving, the above sudoku grid should look like the following:
154873296
386592714
729641835
863725149
975314628
412968357
631457982
598236471
247189563
Explanation / Answer
#include <stdio.h>
int main()
{
int i, j;
int puzzle[9][9]={{*, *, *, *, *, 3, 2, 9, *},
{*, 8, 6, 5, *, *, *, *, *},
{*, 2, *, *, *, 4, *, *, *},
{*, *, 3, 7, *, 5, 1, *, *},
{9, *, *, *, *, *, *, *, 8},
{*, *, 2, 9, *, 8, 3, *, *},
{*, *, *, 4, *, *, *, 8, *},
{*, *, *, *, *, 6, 4, 7, *},
{*, 4, 7, 1, *, *, *, *, *}};
if(solveSudo(puzzle, 0, 0))
{
for(i=1; i<10; ++i)
{
for(j=1; j<10; ++j) printf("|%d", puzzle[i-1][j-1]);
printf("| ");
}
}
return 0;
}
int ifPossible(int puzzle[][9], int row, int col, int no)
{
int rowstrt = (row/3) * 3;
int colstrt = (col/3) * 3;
int i, j;
for(i=0; i<9; ++i)
{
if (puzzle[row][i] == no) return 0;
if (puzzle[i][col] == no) return 0;
if (puzzle[rowstrt + (i%3)][colstrt + (i/3)] == no) return 0;
}
return 1;
}
int solveSudo(int puzzle[][9], int row, int col)
{
int i;
if(row<9 && col<9)
{
if(puzzle[row][col] != 0)
{
if((col+1)<9) return solveSodu(puzzle, row, col+1);
else if((row+1)<9) return solveSodu(puzzle, row+1, 0);
else return 1;
}
else
{
for(i=0; i<9; ++i)
{
if(ifPossible(puzzle, row, col, i+1))
{
puzzle[row][col] = i+1;
if((col+1)<9)
{
if(solveSodu(puzzle, row, col +1)) return 1;
else puzzle[row][col] = 0;
}
else if((row+1)<9)
{
if(solveSodu(puzzle, row+1, 0)) return 1;
else puzzle[row][col] = 0;
}
else return 1;
}
}
}
return 0;
}
else return 1;
}
The input is given in the code itself(as it can be seen) and it outputs the solved Sudoku Puzzle.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.