Latin Squares are also related to the popular Sudoku problems. A Sudoku problem

Question

Latin Squares are also related to the popular Sudoku problems. A Sudoku problem is a 9x9 Latin Square with an additional restriction that the 9x9 grid is subdivided into 3x3 regions which must contain all the numbers 1-9 exactly. We can re-use many of the algorithms from the previous 2 exercises to help with this. To generate a Sudoku problem, you start with a 9x9 Latin square, but it will be slightly different from the previous exercise. It’s a boring Latin Square whose rows have been swapped in a very careful way. To randomize it, you can swap pairs of rows, and pairs of columns, but you can only swap them in limited ways. You can only swap rows 1-3 with another row from 1-3. Likewise, you can only swap rows 4-6 with another row from 4-6. And rows 7-9 can only be swapped with another row from 7-9. The same restrictions apply to the columns. (This is not the best way to create a Sudoku, but it is the easiest.) Once you’ve done enough swapping, you can display it. If you wish, you can randomly decide to display a few blanks instead of numbers in your display; presumably, someone could take your output and fill in the blanks as a relaxing pass-time. For Sudoku problems that you buy in books, the blanked entries usually form a pattern. Don’t worry about that. If you’re using blanks, use somewhere between 30%-40% blanks

Create an Algorithm and pseudocode, then implement your design

Explanation / Answer

Following is the backtracking algorithm of the sudoku 9*9 problem

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.