Sudoku is a fun little logic puzzle where the objective is to fill a 9x9 grid...

 

Transcribed Image Text:

Sudoku is a fun little logic puzzle where the objective is to fill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 sub-grids contain all digits from 1 to 9. Solving one of these involves a lot of testing and back-tracking when numbers don't work out. It's not something a simple program loop can do, but it's perfect for our new tool: recursion. Program requirements: Create a new class called Sudoku.java Inside your main program, create an array of arrays of size 9x9 (see code below). For empty spots, use the number 0. Your program must use a recursive backtracking algorithm to solve for each square. This algorithm will attempt to fill each spot in the array with a number (1-9) and check if the number has been used in the row, column, or the 3x3 sub-grid. To accomplish this with recursion, here is the general flow in pseudo-code: solve Sudoku () end Loop through each row Loop through each column if this row/column combination has no number assigned Loop through numbers 1-9 Check to see if the number is valid here if yes, do solve Sudoku () if no, this row/column combo is unassigned end loop return false end loop for column end loop for row return true For the "is valid" check, you should make three functions: isInRow(), isInColumn(), and isInGrid(). Then call each one for your candidate number. Create and call a method that prints out the board before and after the solution is made Sudoku is a fun little logic puzzle where the objective is to fill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 sub-grids contain all digits from 1 to 9. Solving one of these involves a lot of testing and back-tracking when numbers don't work out. It's not something a simple program loop can do, but it's perfect for our new tool: recursion. Program requirements: Create a new class called Sudoku.java Inside your main program, create an array of arrays of size 9x9 (see code below). For empty spots, use the number 0. Your program must use a recursive backtracking algorithm to solve for each square. This algorithm will attempt to fill each spot in the array with a number (1-9) and check if the number has been used in the row, column, or the 3x3 sub-grid. To accomplish this with recursion, here is the general flow in pseudo-code: solve Sudoku () end Loop through each row Loop through each column if this row/column combination has no number assigned Loop through numbers 1-9 Check to see if the number is valid here if yes, do solve Sudoku () if no, this row/column combo is unassigned end loop return false end loop for column end loop for row return true For the "is valid" check, you should make three functions: isInRow(), isInColumn(), and isInGrid(). Then call each one for your candidate number. Create and call a method that prints out the board before and after the solution is made

Answer rating: 100% (QA)

To create a Sudoku solver program in Java using recursion and backtracking you ca... View the full answer