Project Description
Background
Sodoku is a logic-based numbers puzzle game that has gained popularity over the last several years.
The basic idea of the game is that you have a 9 by 9 grid broken into nine blocks of 3 by 3. Each column and row of the 9 by 9 grid must contain all the numbers from 1 to 9 with no repeats and each 3 by 3 block must also contain all the numbers from 1 to 9 with no repeats.
If you are not familiar with the game, take a little time to play and get familiar at https://sudoku.com/.
Your Task
For this project, you are going to create a Sodoku solver. Given a partially filled grid, your solver program should be able to recursively determine a solution.
We are going to tackle this project in steps:
In the first part of the project, you are going to write the printPuzzle
function. This function should take a 2D vector of characters and print a properly formatted grid.
In the second part of the project, you are going to create the isValid
function. This function should take 4 parameters: the puzzle grid, a row, a column, and a number to test (in that order). The function should return a boolean as to whether the number is valid in that row and column. It is valid if that number doesn’t exist anywhere else in the row, column, or 3 by 3 block.
For the third part of the project, you are going to create the nextEmpty
function. This function should take 3 parameters: the puzzle grid, a row, and a column. The row and column should be passed by reference and updated to contain the next position that is empty on the board. Once an empty cell has been found, the function should return true. If there are no more empty cells on the board, the function should return false.
In the final part of the project is to complete the sodukuSolver
function. This is a recursive function that should take the puzzle as an input (passed by reference) and return true once solved. If a solution is not possible, it should return false.