Admin of the Bestiverse

  • 0 Posts
  • 10 Comments
Joined 2 months ago
cake
Cake day: September 5th, 2024

help-circle









  • 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.