The New Sudoku Players' Forum

[normxxx]

I discovered Sudoku several weeks ago. The main problem in solving such puzzles is usually that you have to keep track of many things and make sure you do not make any careless errors. This does not appeal to me. However, the technical problem of deriving deterministic, 'logical' algorithms appealed to me, especially as two possible algorithms immediately occurred to me.

What we have is a matrix of three sets of nine nine-cell vectors (box, line, and column), or 27 9-cell vectors in all, which are not independent since, as defined, there are only 81 total cells, with each cell having a representation in each of the three vector sets.

Following is the description of a deterministic 'elimination' process composed of several discrete algorithms.

Start by assigning the number sequence "123456789" to each cell of the matrix which is not already occupied by a single digit (singleton).

Algorithm 1:
For each nonsingleton cell of the matrix, reduce its original set of numbers by any unique singletons in that cell's box, line, and column vectors. This is an iterative process which does not complete until no more cells 'reduce' to singleton cells.

Algorithm 2:
For each nonsingleton cell of the matrix, check that there are duplicates for every remaining number in that cell for each box, line, and column vector. If any number is found in a cell which is unique to any of that cell's vectors, force that cell to that number, since it is the only legal position for it. Whenever a cell is forced to a singleton, we redo Algorithm 1.

This approach solved all of the easy and (so far) all of the medium puzzles I have encountered. It did not work for (some of) the "hard" ones.

There are (at least) two further sets of logical, deterministic, related algorithms which can be employed.

For each of the following algorithms, when any number(s) eliminated from any cell results in a singleton digit remaining for that cell, we restart with Algorithm 1 (followed by Algorithm 2).

Algorithm 3a:
Search for matching dupletons in each of the 27 vectors. If a matching pair of dupletons is found, both of their digits can be eliminated from every other cell in the vector in which they occur, since these matching cells absolutely determine the only legal locations of these two digits.
Algorithm 3b:
Search for matching tripletons in each of the 27 vectors. If three matching tripleton cells are found in a vector, all three of their digits can be eliminated from every other cell in the vector in which they occur, since these matching cells absolutely determine the only legal locations of these three digits.
Algorithm 3c:
Search for matching quadrupletons in each of the 27 vectors. If four matching quadrupleton cells are found in a vector, all four of their digits can be eliminated from every other cell in the vector in which they occur, since these matching cells absolutely determine the only legal locations of these four digits. (This can be repeated for five matching quintupletons, six matching sextupletons, etc.)

Algorithm 4a:
Search for three dupletons in each of the 27 vectors, such that they share only three unique digits. If such a triple cell set of dupletons is found, all three of their three (unique) digits can be eliminated from every other cell in the vector in which they occur, since these three cells absolutely determine the only legal locations of these three digits.
Algorithm 4b:
Search for four tripletons in each of the 27 vectors, such that they share only four unique digits. If such a quadruple cell set of tripletons is found, all four of their (unique) digits can be eliminated from every other cell in the vector in which they occur, since these four cells absolutely determine the only legal locations of these four digits.
Algorithm 4c:
Search for five quadrupletons in each of the 27 vectors, such that they share only five unique digits. If such a quintuple cell set of quadrupletons is found, all five of their (unique) digits can be eliminated from every other cell in the vector in which they occur, since these five cells absolutely determine the only legal locations of these five digits. (This can be repeated for six quintupletons of six unique digits; seven sextupletons of seven unique digits; etc.)


I have a 'last resort' algorithm which has been tested (and seems to work OK, if you are patient). Unfortunately for "purity," it is a "trial and error" approach, which are shunned alike by "purists," mathematicians, and computer scientists-- they are not "elegant."

Algorithm 20:
Look for dupleton cells. Having found one, proceed only if there is another dupleton in that cells vector set which matches at least one of its numbers. If so, force the cell to that number and redo Algorithms 1 and 2 until there are no more changes. If we have a solution, fine. Otherwise, we try the second number for the cell (if it passes the 'nonuniqueness test'), or go on to the next dupleton. This has solved the "hard ones" I've tried so far.

[Karyobin]

I know I don't have to reply to this post, but after seeing how many people have read it, I can't help feeling you may want some form of response, so I take it upon myself. That said, I really don't know how to respond to your post without my being accused of being nasty (coz of my simplistic manner), but either you've never read any of the online or even published documents on sudoku, or else it would seem that after solving a few, you attained an incomplete idea of the general approach. You say you don't like errors - there really is no need or room for errors.

In your favour, you've managed to apply previously unused (and in my case unrecognisable) words to well-known and established constructs, suggestive that you've made an attempt to formalise something you feel you have discovered. Unfortunately, everyone else has discovered it too. For further far more interesting and intricate techniques, I suggest you read some of the excellent explanations contained in:

http://www.angusj.com/sudoku/hints.php

and

http://www.simes.clara.co.uk/programs/sudokutechniques.htm

After all, no sense reinventing the wheel eh?

P.S. By the way, you seem to be posting the same message OVER AND OVER again - is this due to lack of imagination or an over-inflated ego? Surely a 'retired computer scientist' would know and understand this most heinous of faux-pas?

[normxxx]

Thank you.

either you've never read any of the online or even published documents on sudoku, or else it would seem that after solving a few, you attained an incomplete idea of the general approach.

Actually, I immediately realized that, as sudoku had been around for several? years at least, it was unlikely that I would have discovered anything new. In fact, the reverse. (But I didn't see anything in your references corresponding to the complete set of my Algorithms 3 and 4.)

Thanks for moving my original post to the programmers thread-- I hope to persue some of that. But, as I said originally, I am more interested in the algorithms than either the programing or doing them by hand.

I just hoped someone (who turned out to be you) would lead me to a rich source of algorithms which I had not yet figured out-- there were several ones new to me on your first reference; I have not checked the second reference very carefully as yet.

However, I didn't see anything about my algorithm 3c or 4-- but I have not checked all of the your suggested algorithms thoroughly as yet. I would assume that 4a, at least, is somewhere among them.

[normxxx]

Correction: It appears my algorithms 1, 2, and all of 3 are covered by the conventional "logic."

However, I do not see anything corresponding to my algorithm 4.

[tso]

Correction: It appears my algorithms 1, 2, and all of 3 are covered by the conventional "logic."

However, I do not see anything corresponding to my algorithm 4.

Sorry, nothing new to see here.

4a is just a special case of "naked triples"
4b is just a special case of "naked quads"
4c is just a special case of "naked quints"

Described many places, in and out of this forum.

The generalized rule -- N candidates among N cells -- has been called "disjoint subsets".

See: http://www.angusj.com/sudoku/hints.php, scroll down to "Naked"

See: http://www.simes.clara.co.uk/programs/sudokutechnique5.htm

For a tediously specific description, look here, scroll down to TSO.

[normxxx]

I AM NOT SURE THAT IS TRUE!

"Naked Triples" would be, for example, {1,2,3};{1,2,3};{1,2,3} —
in other words, my 3b.


An example of 4a is: {1,2,-};{1,-,3};{-,2,3} ==> 1,2,3 can be eliminated from all other vector cells.

An example of 4b is: {1,2,3,-};{1,2,-,4};{1,-,3,4};{-,2,3,4} ==> 1,2,3,4 can be eliminated from all other vector cells.

4a and 4b are not among your examples— exactly what is the rule encompassing all "naked duples, triples, quads, etc.?"

[tso]

I AM NOT SURE THAT IS TRUE!

"Naked Triples" would be, for example, {1,2,3};{1,2,3};{1,2,3} —
in other words, my 3b.


An example of 4a is: {1,2,-};{1,-,3};{-,2,3} ==> 1,2,3 can be eliminated from all other vector cells.

An example of 4b is: {1,2,3,-};{1,2,-,4};{1,-,3,4};{-,2,3,4} ==> 1,2,3,4 can be eliminated from all other vector cells.

4a and 4b are not among your examples— exactly what is the rule encompassing all "naked duples, triples, quads, etc.?"

Please click on the links I gave in the previous post and read them carefully. Your question has been answered in each place.

This is an example of a "naked pair":

Code: Select all

[12][12]

There are a total of TWO candidates in TWO cells. No matter how you distribute them, those two candidates will be eliminated them from the rest of the row, etc.

Each of these are perfectly valid examples of "naked triples":

Code: Select all

[123][123][123]
[123][123][12]
[123][13][12]
[23][13][12]

There are a total of THREE candidates in THREE cells. No matter how you distribute them, the three candidates must all be used to fill the three cells, eliminated them from the rest of the row, etc.


These are all perfectly lovely examples of "naked quadruples":

Code: Select all

[1234][1234][1234][1234]
[1234][1234][1234][123]
[1234][1234][124][123]
[1234][134][124][123]
[234][134][124][123]
[12][23][34][14]
[12][34][123][234]
[1234][13][24][124]

... and quite a few others.

Four candidates, four cells.

(Also, each candidate is in at least two cells -- otherwise you can reduce -- for example:

Code: Select all

[124][13][24][124]

... has only one 3 -- the other three cells form a naked triple.)

Then general rule is N candidates in N cells eliminates those candidates for the rest of the row, column or box.


I just scrolled back and realized we've answered this question several times. Please read all the links. The explain this clearly, some with pictures.

[normxxx]

Sorry if I made you repeat yourself, but I am trying to understand, and I am very new to sudoku.

However, I think I have all of the "naked" combinations down. I am now working on the "hidden" variations of same...

I do thank you for your patience.

Can you recommend a good book on same, beginner to advanced? (Preferably oriented to 'solvers,' as I would like to come up with a set of 'rules' that could be easily programmed.)