Write a program to solve a sudoku! Given a partially filled 9×9 2D array ‘grid[9
ID: 3776878 • Letter: W
Question
Write a program to solve a sudoku! Given a partially filled 9×9 2D array ‘grid[9][9]’, the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9.
I have posted 3 input files: sudoku1.txt, sudoku2.txt and sudoku3.txt
Problem Analysis & Design - Think about how you will need to solve this problem. You should do an object oriented solution which creates a Sudoku class to hold and manipulate a puzzle, and a main program to control things. Think about the data and methods needed for the Sudoku class. Read through all the phases below for some ideas on how to break things down.
Step 1: Create a main program which should handle the input processing details. Make it so that it will get the name of an input file from the user (test files have been given to you), create a puzzle object, read from the file to initialize the puzzle, display the initial puzzle on the screen then the solved puzzle. The last two operations should call methods in your Sudoku class to do the work. Write the bodies of these methods. Compile, run and test.
Step 2: In your Sudoku class, create a two-dimensional array of 9 rows and 9 columns. Initialize this array with values from the Sudoku text files by passing the scanner object to the constructor.
Step 3: Write a toString()method to return the contents of the 2-dimensional array as a string.
Step 4: Write a method call checkConflict() that returns true if a conflict exist and false if not. A conflict is detected when a new number placed at a particular location already exist within that row, column or sub-grid of size 3×3.
Step 5: Implement the recursive backtracking solution for solving Sudoku sudokuSolver() . The algorithm is given below.
Backtracking Algorithm
Like all other Backtracking problems, we can solve Sudoku by one by one assigning numbers to empty cells (empty cell is indicated by value 0). Before assigning a number, we check whether it is safe to assign. We basically check that the same number is not present in current row, current column and current 3X3 subgrid. After checking for safety, we assign the number, and recursively check whether this assignment leads to a solution or not. If the assignment doesn’t lead to a solution, then we try next number for current empty cell. And if none of number (1 to 9) lead to solution, we return false.
Explanation / Answer
#include <stdio.h>
#define UNASSIGNED 0
#define N 9
bool FindUnassignedLocation(int grid[N][N], int &row, int &col);
bool isSafe(int grid[N][N], int row, int col, int num);
bool SolveSudoku(int grid[N][N])
{
int row, col;
if (!FindUnassignedLocation(grid, row, col))
return true; // success!
for (int num = 1; num <= 9; num++)
{
if (isSafe(grid, row, col, num))
{
grid[row][col] = num;
if (SolveSudoku(grid))
return true;
grid[row][col] = UNASSIGNED;
}
}
return false; }
bool FindUnassignedLocation(int grid[N][N], int &row, int &col)
{
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
if (grid[row][col] == UNASSIGNED)
return true;
return false;
}
bool UsedInRow(int grid[N][N], int row, int num)
{
for (int col = 0; col < N; col++)
if (grid[row][col] == num)
return true;
return false;
}
bool UsedInCol(int grid[N][N], int col, int num)
{
for (int row = 0; row < N; row++)
if (grid[row][col] == num)
return true;
return false;
}
bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num)
{
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row+boxStartRow][col+boxStartCol] == num)
return true;
return false;
}
bool isSafe(int grid[N][N], int row, int col, int num)
{
return !UsedInRow(grid, row, num) &&
!UsedInCol(grid, col, num) &&
!UsedInBox(grid, row - row%3 , col - col%3, num);
}
void printGrid(int grid[N][N])
{
for (int row = 0; row < N; row++)
{
for (int col = 0; col < N; col++)
printf("%2d", grid[row][col]);
printf(" ");
}
}
int main()
{
int grid[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0}};
if (SolveSudoku(grid) == true)
printGrid(grid);
else
printf("No solution exists");
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.