JavaScript Sudoku solutions

Bob Hanson · Posted: Wed Oct 05, 2005 5:42 pm Post subject: JavaScript Sudoku solutions

I'm sure this is a VERY old topic, but I just joined this forum, so I'm clueless.

I was experimenting with a page:

http://www.stolaf.edu/people/hansonr/sudoku

when I realized that X-Wings and Swordfish and such can be very easily coded. I've made a note of this at the Sudoku Wiki discussion site, but probably this is a better forum. The JS code is all in the index.htm file there.

I'm wondering what other solutions people have come up with that treat X-Wings and Swordfish and such all as the same issue.

Are there even more issues than these?

By the way, Angus, aren't "hidden pairs" just "naked n-sets", where n is the number of open positions - 2?

I'm looking for killer Sudoku puzzles that break this solver. (I'm guessing that's easy for the more experienced among us to find. )

Please pass them on. (I've set up this page so it can load puzzles in a variety of forms from straight strings of numbers to blocks of text. I'm a bit surprised others haven't caught onto this idea. Makes testing specific boards very easy.

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

Lummox JR · Posted: Wed Oct 05, 2005 9:27 pm Post subject:

Well, I'm guessing puzzles to break this could be easy to find, because I've seen many puzzles that require techniques more advanced than swordfish. Moreover, this won't actually catch all swordfish.

One method you're missing is finding naked singles--where a cell can only have one possible value. Crosshatching will find hidden singles in a box. I also see no method for finding hidden singles in a column or row. These methods are quite common and appear in sudoku grids of easy or moderate difficulty. Your subset test will find these, because each naked or hidden single among a set of N choices has a subset of N-1 to go along with it.

The technique you call row/column range checking is more commonly referred to as either pointing pairs/triples or box-line intersections, which are basically two forms of the same thing. In a pointing pair or triple, the only possible placements for a digit in a box are all in the same row or column, so other placements for that digit in the same row or column can be eliminated. In a box-line intersection, the only possible placements in a particular row or column are all in the same box, so other placements in that box can be eliminated.

Subsets are definitely an important test. Naked and hidden subsets are basically two sides of the same coin. Realistically speaking you should almost never find quads, since they can only appear (in the absence of simpler subsets anyway) in cases where you have 8 or 9 candidates/cells to check. The reason I say naked and hidden subsets are basically the same thing is that where one exists, so does the other. If you have a naked triple in 5 cells, you also have a hidden pair.

The X-wing and swordfish analysis I'm not sure is so right. Your "circuit analysis" approach is actually equivalent to a technique better known as fishy cycles, but while all X-wings can be fishy cycles, the same is not true of all swordfish. To see what I mean, look at your swordfish example where the blue lines cross at (6,5). If 5 was a possibility there--which I know it's not because there's already a 5 in that box--you'd still have a valid swordfish.

X-wings and swordfish are in fact not directly related to fishy cycles at all; they're a positional form of the subset test. Instead of looking for subsets of digits and positions in a house (box/column/row), you're looking for subsets in columns and rows. The definition of an X-wing or swordfish is that in a set of N columns, all the placements for a particular digit must occupy no more than the same N rows; other candidates in those rows may be eliminated. You can swap the rows and columns and get the same logic, in much the same way that a naked subset always has a hidden subset along with it. Your example shows two swordfish in the 5's, one by column (blue) and one by row (red).

Now it seems you're on the right track with another way you described circuit analysis, but if you're aware it's a subset test then I'm not sure why you'd choose "cicruit analysis" as a name, since subsets are not circuits. Also, there's a little problem with this:

Bob Hanson · Posted: Wed Oct 05, 2005 11:00 pm Post subject:

Thank you for the very extensive response!

I'll apologize up front for inventing my own lingo -- I'll make an effort to conform with accepted terminology as I get the feedback.

Actually, it should find hidden or naked anthing. (I think you mean "hidden singles" because a "hidden" anything is really a "naked" something else.

1235 45 6 27 8 76 35

is "hidden" 1 but a "naked" 345678 because in those other cells there is no 1 (that's what it means to be hidden, I think), so they are "naked". Right? So we are finding all naked anythings -- there's no limit -- so I think all hidden singles will be found. The simplest examples:

123 23 23

are of that sort.

Also, the program uses cross-hatching first, and will definitely find any such place where there is only one possibility and fill it in. That's its first method. So that's definitely no issue.

The program extends "box-line intersections" to doubly paired adjacent boxes, by the way. Is that discussed somewhere?

[ m or n ] [ m or n ] [ ]
[ m or n ] [ m or n ] [ ]

----------- ------------------ [must be m or n here ]

Although I describe the X-wing business as "circuit analysis" you can see from the code that it is not really doing that. It is just mapping all of the row subsets onto other rows and finding any possible alignment of n rows with n columns. I'm pretty sure that takes care of ANY type of "swordfish" including all possible missing/present corners. As I said, it has passed the test with everything I've thrown at it, but I'm not so confident to say there wouldn't be other "superstructures" that it would miss. But I am confident that it will find all X-wing/swordfish sorts of things.

I can see that my statement with the two points is not tight enough. Like you say, one or the other -- the set of rows or the set of columns -- must be clear of the candidate for this to work. I'll definitely change that wording tonight.

I assure you what you suggest is in fact what the code does. Right -- it chooses rows first, finds the set, then eliminates the column elements and goes on. The test is repeated on columns separately. I thought it was neat the way the code doubly iterates -- once to pass on to try a totally different combination of rows, another to try a different combination of columns until all possible subsets are quantified. It really shows the power of iterative code (Hey, some of us have been around long enough to remember when that became available!).

In the end all the functions pop back through the originator to deliver either a "found one" or "nothing there of any sort" outcome. I'm pretty sure I've got it iterating so it will always return the SIMPLEST of swordfishy things present. But I've certainly seen "level-6" swordfish turn up, and I think it's possible to go to 7x7. Maybe not.... Anyway, if it's possible, this will find it. (What's fun is to take a really simple Sudoku, turn off the subset elimination option and try to solve it JUST with swordfish-like (what do I call these?) things. That's where the really big ones come in. Of course, no one would really do this. ....or would they....

The key is that if any union of parallel row/column candidate subsets has the same number of column-elements as rows we are done. And the code is designed to track down all possible unions of subsets. So that should be that....

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

Lummox JR · Posted: Wed Oct 05, 2005 11:54 pm Post subject:

angusj · Site Admin

Bob Hanson · Posted: Thu Oct 06, 2005 3:49 am Post subject:

This is very helpful to me. In fact, here's something that I'm just now realizing. Forgive me if this is "common knowledge":

For all candidates, at all times during a puzzle's solution, there is at least one "swordfishy thing" there. That large one basically allows for the "cross-hatch" solution. That is, there is always an n x n grid of some size that all possible solutions for a given candidate number to fit onto, with at least two possible solutions on each row and each column. Nothing too interesting there.

But in some cases, like the subset possibilities in a single row, block, or column, there are subsets of this larger grid that allow for eliminations to be made. That's all an X-wing or Swordfish is.

I guess I sort of lucked into this -- my little iteration function does in fact return the FIRST n x n grid it finds, which because of the way I coded that function returns the SMALLEST that it can find. In the end it only reports its find if it also results in the elimination of a possibility -- otherwise it just moves on. But where there is one, there are two.

In the case of the two 3x3 SFs at

http://www.stolaf.edu/people/hansonr/sudoku/explain.htm

there is a main 6x6 that is being subdivided into two 3x3. Which leads to an interesting idea: If there is one, are there always two?. I think perhaps there have to be. For example, at:

http://www.stolaf.edu/people/hansonr/sudoku/index.htm?,-9,-8,,-1,-2,,-4,,-5,-6,-2,-3ttt,,-9ttt,-6,,-1,,-3,-6t,-5,-9,,-1,,-7ttt,-2ttt,,-6,-4,-5,-3,,-4,,-5,-7,,-8,-2

(I hope that transmits. If not:

.98 .12 .4.
562 3.. ...
... ..9 ...
... ... 6.1
.36 ... 59.
1.7 ... ...
... 2.. ...
... ..6 453
.4. 57. 82.

You can clip that into the Sudoku Assistant using the "number block input link.")

There's a easily identifyable 2x2 X-Wing. But there's also a 4x4 and a 6x6. Is that all this is? I suppose there's a theorem there: For every nxn subset grid there is another mxm subset grid that will (I'm guessing) eliminate the same set of points. oy. That rings true...

In fact, if you consider the solved numbers as "1x1"s then we of course a 9x9 for all at all times. Our goal is to reduce that to 9 1x1s. That is, the entire project can be seen in the framework of "X-Wing-things".

OK, I see.... that's what cross-hatching IS in fact -- just removing the 1x1 subsets from a larger n x n set. Sure.

Is this just old hat for Sudoku officanados?
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

dukuso · Posted: Thu Oct 06, 2005 5:34 am Post subject:

Bob Hanson wrote:

>The key is that if any union of parallel row/column candidate subsets >has the same number of column-elements as rows we are done. And >the code is designed to track down all possible unions of subsets. So >that should be that....

I'm too lazy to walk through all the long posts here carefully but that
sounds to me like "Hall's marriage theorem" .
See theorem 5 page 14 in this document:
http://www.cs.cornell.edu/~vanhoeve/papers/alldiff.pdf

is it the same ?

Bob Hanson · Posted: Thu Oct 06, 2005 11:47 am Post subject:

Well, not being a mathematician, that will take some time to peruse. But it looks like what I am going to say next is PROBABLY a simple 3D subset of that that paper is all about.

OK, I am going to write a page -- an offshoot of the Sudoku Assistant -- that will demonstrate something I've haven't seen before (OK, in the one week I've been working on this....)

Imagine pulling out 9 layers of the Sudoku, one per candidate number. Stack these layers one above the other to make a 9x9x9 cube.

The common {p,q,r} {p,q} {q,r} subset elemination tactic is the VERTICAL equivalent then of the single candidate HORIZONTAL n x n grid analysis.

That, precisely, I think, is ALL there is to a Sudoku, fundamentallly. Starting with 9 9x9 subsets (a little less, because we have some givens), reduce this to a set of 81 1x1 subsets.

My intuition is that this solves any possible standard Sudoku. How could it not?

That suggests a single 2D-function similar to my analyzeCandidate(k) that will do the job: analyzeX(x,y,z)

If I'm recreating the wheel, please point me to this function.

Another of my activities, by the way, is being on the development team of an open-source molecular visualization applet, Jmol

http://sourceforge.net/projects/jmol

Of course, all chemical structures can be modeled as simple 3D graphs. This applet allows the creation of 3D graphs on the fly. I think I'll write the definititive 3D Sudoku analysis using Jmol. What do you think? Am I too late? Anyone want to help?

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

dukuso · Posted: Thu Oct 06, 2005 2:29 pm Post subject:

>Well, not being a mathematician, that will take some time to peruse.

empty sudoku is a constraint satisfaction problem with 81 variables
each with domain {1,2,..,9} and 27 alldifferent constraints,
9 for rows, 9 for columns, 9 for blocks
alldiff(x1,x2,x3,x4,x5,x6,x7,x8,x9)
...
alldiff(x61,x62,x63,x70,x71,x72,x79,x80,81)

when e.g. there is a 5 in cell 34 then just set the domain
D(x34)={5}

etc. I hope you see the pattern.

Choose one constraint, e.g. column 3

Now Hall's theorem says that that you can fill it with 9 different
symbols, iff for any subset K of {x3,x12,x21,x30,x39,x48,x57,x66,x75}
there are at least |K| different candidates available.

This ignores, what happens with the other constraints
(=rows,columns,blocks) , it only dictates when that column 3 can be filled.
Ah yes, the domain of a variable is just the set of candidates
which can go into that cell.

Take e.g. K={x21,x39,x48} then the number of different candidates
for these 3 cells must be at least 3.

This is pretty clear, however the theorem says that this
is also sufficient.

But even if this is satisfied for all the 27 constraints, that doesn't
yet mean, that the sudoku has a solution.

>But it looks like what I am going to say next is PROBABLY a simple
>3D subset of that that paper is all about.
>
>OK, I am going to write a page -- an offshoot of the Sudoku Assistant
>-- that will demonstrate something I've haven't seen before (OK, in
> the one week I've been working on this....)
>
>Imagine pulling out 9 layers of the Sudoku, one per candidate number.
>Stack these layers one above the other to make a 9x9x9 cube.
>
>The common {p,q,r} {p,q} {q,r} subset elemination tactic is the

I'm afraid it's not so common to me

>VERTICAL equivalent then of the single candidate HORIZONTAL n x n
>grid analysis.
>
>That, precisely, I think, is ALL there is to a Sudoku,
>fundamentallly. Starting with 9 9x9 subsets (a little less,
>because we have some givens), reduce this to a set of 81 1x1 subsets.
>
>My intuition is that this solves any possible standard Sudoku.
>How could it not?

my intuition is, that it doesn't. But I didn't yet understand,
I only have an idea what you mean

>That suggests a single 2D-function similar to my analyzeCandidate(k)
>that will do the job: analyzeX(x,y,z)
>
>If I'm recreating the wheel, please point me to this function.
>
>Another of my activities, by the way, is being on the development
>team of an open-source molecular visualization applet, Jmol
>
>http://sourceforge.net/projects/jmol
>
>Of course, all chemical structures can be modeled as simple 3D graphs.

you're loosing information, i.e. the distances of the molecules

>This applet allows the creation of 3D graphs on the fly.
>I think I'll write the definititive 3D Sudoku analysis using Jmol.
>What do you think? Am I too late? Anyone want to help?

as it happens I wrote about "3doku" here:

http://www.sudoku.com/forums/viewtopic.php?t=44&start=393

just some hours ago.

is it similar to what you mean ?
Viewing the digit d in a sudoku-cell (x,y) as the z-coordinate
of an item (piece,binary 1) located at (x,y,d).
Then we are looking for a configuration of 81 mutually nonattacking
pieces in that 9*9*9-cube.

-Guenter.

Bob Hanson · Posted: Fri Oct 07, 2005 8:28 am Post subject:

Well, I'll be darned! It works. The following little doubly-recursive JavaScript function, when supplied the correct parameters, finds

naked sets
hidden sets
X-wings
Swordfish
Any similar structure of any dimension

Sure enough, all these are the same, conceptually. See for an implementation:

http://www.stolaf.edu/people/hansonr/sudoku

No backsearching, no guessing, just straight set analysis.
Recursive functions are great!

I'll follow this up with a 3D-rotatable version that clearly demonstrates why all these are the same thing.

And I'm still hoping someone will send me a Sudoku this code won't solve.

function analyzeX(z,type,iscanfirstindex,List,ipt,jlist,ilist,nx,ny,msg){

if(ipt>=List.length||nx>maxdim||ny>maxdim)return 0
var maxlen=List.length/2+1
analyzeX(z,type,iscanfirstindex,List,ipt+1,jlist,ilist,nx,ny,msg)
if(showlist)return 1
var i=List[ipt] //another row/col
ilist+=Pwr2[i]
if(iscanfirstindex){
jlist=jlist | Possible["X"+type][i][z]
}else{
jlist=jlist | Possible["X"+type][z][i]
}
nx=xNum(jlist)
ny++
if(nx>maxlen)return 0
if(ny==nx && analyzeFoundX(z,type,iscanfirstindex,jlist,ilist,nx,msg))return 1
return analyzeX(z,type,iscanfirstindex,List,ipt+1,jlist,ilist,nx,ny,msg)
}
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

gsf · Posted: Fri Oct 07, 2005 2:48 pm Post subject:

Bob Hanson · Posted: Fri Oct 07, 2005 6:44 pm Post subject:

fascinating. What else is know about 1-constrainedness?
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Bob Hanson · Posted: Fri Oct 07, 2005 6:46 pm Post subject:

By the way, I did turn this into 3D -- not a 9x9x9 puzzle, but a 3D deconstruction of the puzzle showing how X-Wings are identical to simple subset elimination, but in a different dimension.

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