We will write pseudocode to solve a Sudoku based on a backtracking approach. A Sudoku is a
Question:
We will write pseudocode to solve a Sudoku based on a backtracking approach. A Sudoku is a 9 by 9 puzzle where puzzler attempts to fill in each cell with numbers from 1 to 9 satisfying three criteria:
- Each row has the number from 1 to 9 exactly once.
- Each column has the numbers from 1 to 9 exactly once.
- Each of the 9 three by three sub-grids has the numbers from 1 to 9 exactly once.
The following is an example puzzle on the left with the 9 sub-grids bolded and the accompanying solutions on the right.
For this we will introduce a new SUDOKU data type with the following operations
• MAKEEMPTYSUDOKU • ITEM(S, row, col)
• FILL(S, row, col, number) • SUBGRID(S, row, col)
• BLANK(S, row, col) • ROW(S, row)
• ISBLANK(S, row, col) • COL(S, col)
Above, ROW and COL return a list consisting of the numbers in the given row/column. SUBGRID returns a list of the numbers in the same sub-grid as the cell in row, col. The sub-grid is one of the nine sub-grids found above. For example, SUBGRID(S, 5, 5) would return the 9 numbers in the middle most sub-grid as a list. FILL returns a new SUDOKU grid with the number _lled in position (row, col).
Modify the backtracking algorithm from the course to write a Sudoku solver, that is, write an algorithm that solves the following problem:
SOLVE SUDOKU(S)
INPUT: A partially filled Sudoku S that obeys the above constraints.
OUTPUT: A filled Sudoku S satisfying the above constraints or False if impossible.
You do not need to be too formal with your pseudocode approach but should be able to describe your algorithm to a competent reader.
Essentials Of Business Statistics Communicating With Numbers
ISBN: 9780078020544
1st Edition
Authors: Sanjiv Jaggia, Alison Kelly