Starting over

King Wonka · Posted: Fri Dec 16, 2005 3:36 pm Post subject: Starting over

It's kinda hard to program a technique that you don't really understand and I'm not one to lift code so.... I have to start over and get this right in my brain of how dancing links work.

I did some reading on Wikipedia on the dancing links algorithm.

Ruud · Site Admin

Hi Anthony,

I've placed an explanation of Dancing Links here:
http://home.quicknet.nl/qn/prive/r.vanderwerf/dancinglinks.htm

It may give you some ideas about setting up the data structures.

Ruud.
_________________
Meet me at sudocue.net

Bob Hanson · Posted: Fri Dec 16, 2005 4:29 pm Post subject:

Ruud, I think with your help I could understand this.

I read:

The viewer shows all 324 constraints that must be met. In terms of Dancing
Links, these are the columns. With an empty grid, there are 9 candidates
competing in each of these constraints. A candidate is a particular digit
assigned to a cell. Each candidate must fight for its existence in each of the 4
major areas. When it loses in one of them, it is removed from all 4 areas.
The candidates are represented by a blue rectangle in each of the 4 areas.
When a constraint has declared a winner, that candidate will be shown in
green.

But then on the left there is a list of Row numbers instead of digits, and I
guess I don't understand that histogram. Why are there multiple blue
boxes in a vertical stack?

Could you just read across the top row and say what that means?

Maybe just show us the configuration corresponding to this.

Thanks.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Ruud · Site Admin

The first stack shows the "cell" constraints.
- Cells are identified by Row (side) and Column (top).

The next 3 stacks show the "unit" constraints, rows, columns and boxes.
- Units are identified by number (top) and digit (side)

Each constraint has upto 9 candidates. These are represented by the blue boxes. There is not enough room to show which candidates, but you always have the main Sudo Cue window that shows the remaining candidates.

When a constraint has only one box, it is green, and the constraint is "solved" or "satisfied". When there are 2 blue boxes in a constraint, there are 2 candidates remaining. So, in the example, Row 1 and 5 have 2 candidates for digit 1, row 6 has 3 candidates left.

There is no connection between constraint groups which are side-by-side. However, when you look at the last 3 stacks, you can see how each digit is solved in the 27 unit constraints. The total number of candidates per digit is the same for rows, columns and boxes.

So,

this is not the full columns and rows as used by DLX. It is a condensed visualization. The full DLX grid has 729 rows. That would leave 1 pixel per row. And I would have to place all 324 constraints side-by-side. Not enough room to be informative. This condensed view shows only the nodes that are actually used.

Ruud.
_________________
Meet me at sudocue.net

Bob Hanson · Posted: Fri Dec 16, 2005 5:41 pm Post subject:

Ah, OK. But there is room -- why not just color the box of the specific
candidate blue rather than stacking them? Actually, I think this would be
REALLY nice, because you would instantly see the naked tuples,
X-Wings and such right there in front of you.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr