How Sudoku like problems can be represented in Exact Cover Problems ?
from unknown_user@lemmy.ml to programming@programming.dev on 05 Sep 2024 10:00
https://lemmy.ml/post/19957977

I understand that Exact Cover is a problem where you want to select a subset of rows from a binary matrix such that each column contains exactly one ‘1’. What specific constraints need to be included in the matrix to ensure that the solution adheres to the rules of Sudoku (e.g., unique numbers in rows, columns, and subgrids)? provide a simple example of a Sudoku puzzle and its corresponding Exact Cover representation may be 3x3 sudoku puzzle for example ? I tried reading the Wikipedia article and various links, but I couldn’t understand Exact Cover, even though I am familiar with the DLX structure.

#programming

threaded - newest

patrick@lemmy.bestiver.se on 05 Sep 2024 18:03 collapse

Hmm, I could have sworn I had code for this but I’m not able to find it. I wrote a DLX impl many years ago and used it for a few things, and I wrote several different sudoku solvers, but I don’t seem to have ever used my DLX impl to solve sudoku puzzles…

What you need to do is create a row for every possible entry and location in the puzzle. So you will have a row representing every single possible entry option. 9 options x 81 total squares = 729 total rows.

The columns in your Exact Cover Matrix represent all the different constraints, where each column must be unique in the solution.

  • You’ll have 81 columns that represent just the location (you can only have 1 number in each of the 81 boxes).
  • For every Row/Column in the Sudoku Puzzle, you will have 9 columns to represent the 9 different numbers. (e.g you can only have a single “5” in every Row of the Sudoku)
  • For every 3x3 box in the Sudoku puzzle, you’ll also have 9 columns for the 9 different numbers.

So your Exact Cover Matrix will need 324 columns = 81 (squares) + (9 (numbers) * 9 (rows)) + (9 (numbers) * 9 (cols)) + (9 (numbers) * 9 (boxes))

When you fill out all the rows, you’ll place 1’s in all the columns that that specific entry aligns with. Take the example of the row corresponding to the entry “5” in the Sudoku Puzzles top left box. That row in your Exact Cover Matrix will contain:

  • A 1 in the column representing that specific box.
  • A 1 in the column that represents the number 5 in the first Sudoku Row.
  • A 1 in the column representing the number 5 in the first Sudoku Column.
  • A 1 in the column representing the number 5 in the top left Sudoku Box.
  • 0’s everywhere else

To feed a specific puzzle into your solver, it kinda depends on the solver, you just need to force the output to contain those specific rows.