4.2 An application: Sudokus In the sudoku problem, a partially filled 9 × 9 grid

Question

4.2 An application: Sudokus In the sudoku problem, a partially filled 9 × 9 grid is to be completed with numbers in the range [1,2, meeting the following constraints:1 ,9, while each row should have exactly one occurrence of each number » each ccurrence of each number A particular instance of the sudoku problem, i.e. a specific, partially completed grid, shall be called a sudok?u column should have exactly one o puzzle, or a sudoku. For example, this sudoku puzzle 5 1 |217| 8 171 1 1 16141 1 34 7 6 8 25| accepts, among many others, the following solution: 5 6 4|9|12|7 8 3 6 3 5|4 2 7 89 1 79 6 8 4| 13 | 5 2 | 3 48|19 5 217 6| 14?1|3|5|619|218| |1|219|516|814|31? This exercise does not ask you to solve the sudoku above, since the solution is given! Instead you are to restate the sudoku problem as an exact cover problem: 1. (10 pts) Describe the structure of the matrix of 0s and 1s that is suitable for solving any sudoku puzzle: what do you represent in the columns? How many of them do you need? What do you represent in the rows? Do all sudoku puzzles ask for the same number of rows? Why? Be specific and precise in your wording; draw a diagram if it adds clarity to your answer

Explanation / Answer

Solving a sudoku puzzle

The Algorithm of solving the sudoku puzzle using the 0's and1's matrix is called " Method X" its been formulated by

Donald knuth.(Also called exact cover problem)

___ANSWERS___

1. Structure of the matrix of 0's and 1's needed for solving sudoku puzzle is 9x9.

--->The things that are represented in column area are as follows

-- Region constraint :- Only 1 instance of a number can be in a region

-- Column constraint :- Only 1 instance of a number can be in a column

-- Position Constraint :-   Only 1 number can occupy a cell

--Row Constraint :- Only 1 instance of a number can be in the row.

-->Each number comes with its own set of constraint therfore the number of columns would be size(square) *4

here size is 9. terfore columns would be 9*9*4 = 324.

---> No, the no of rows required would be according to size, thee rows represent every single possible position for every number. Therefore, there are SIZE ^ 3 rows. In a 9x9 sudoku, this would be 729 rows..

  

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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