Programming

17314 readers

70 users here now

Welcome to the main community in programming.dev! Feel free to post anything relating to programming here!

Cross posting is strongly encouraged in the instance. If you feel your post or another person's post makes sense in another community cross post into it.

Hope you enjoy the instance!

Rules

Follow the programming.dev instance rules
Keep content related to programming in some way
If you're posting long videos try to add in some form of tldr for those who don't want to watch videos

Wormhole

Follow the wormhole through a path of communities !webdev@programming.dev

founded 1 year ago

MODERATORS

snowe@programming.dev

Ategon@programming.dev

MaungaHikoi@lemmy.nz

How Sudoku like problems can be represented in Exact Cover Problems ? (lemmy.ml)

submitted 2 months ago by unknown_user@lemmy.ml to c/programming@programming.dev

1 comments fedilink hide all child comments

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.

you are viewing a single comment's thread
view the rest of the comments

[–] patrick@lemmy.bestiver.se 1 points 2 months ago

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.