How a human beeing thinks

Advanced methods and approaches for solving Sudoku puzzles

How a human beeing thinks

Postby Pyrrhon » Sun May 07, 2006 7:36 am

There is a aim of some interesting sudoku programs to think like a human beeing. But it is a open question is how such a being is thinking.

I like to suggest a little experiment here. I have a sudoku problem which is solved in different ways by different programs. (I've tested Simple Sudoku, Sudoku Susser, SudoCue, and the online solver on scanraid and no pair of these programs has the same route even if we only consider the main points, the last one has not found the solution.)

Please solve the sudoku as human beeing (not with hints of a computer program and write here in this thread the techniques you used in there order (you should skip naked and hidden singles)
for example your result could be:

hidden triple, XY-wing, XYZ-Wing, hidden pair

If some user have given there way we can discuss the result comparing this with the coumputer
pathes. Please read the other comments in this thread after you have found your own path. If you have not solved the sudoku your path is also interesting for a disussion about the question how human beeings solve sudoku.

Code: Select all
...5.....
.5..2.19.
..9.38.7.
3.....4..
.71...96.
..4.....8.
1.89.5..
.98.7..2.
.....4...
Pyrrhon
 
Posts: 240
Joined: 26 April 2006

Invalid puzzle

Postby keith » Sun May 07, 2006 1:12 pm

This puzzle is not valid. For example, there are two values <8> in C3.

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Re: Invalid puzzle

Postby ronk » Sun May 07, 2006 3:40 pm

keith wrote:This puzzle is not valid. For example, there are two values <8> in C3.
Try this ...
Code: Select all
...|5..|...
.5.|.2.|19.
..9|.38|.7.
---+---+---
3..|...|4..
.71|...|96.
..4|...|..8
---+---+---
.1.|89.|5..
.98|.7.|.2.
...|..4|...
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

One solution

Postby keith » Sun May 07, 2006 4:41 pm

I did this by hand, keeping notes. Then I redid it in Susser. Here is the log:

R1C6 has been set to <9>.
R9C9 has been set to <9>.
R6C1 has been set to <9>.
R4C4 has been set to <9>.
R3C9 has been set to <5>.
R2C1 has been set to <8>.
R4C2 has been set to <8>.
R5C5 has been set to <8>.
Possibility <7> removed from R2C3
Possibility <4> removed from R1C1
Possibility <4> removed from R3C1
R1C5 has been set to <4>.
R2C3 has been set to <3>.
R2C9 has been set to <4>.
R5C4 has been set to <4>.
R7C8 has been set to <4>.
R3C4 has been set to <1>.
R3C2 has been set to <4>.
R1C1 has been set to <1>.
R8C1 has been set to <4>.
Possibility <5> removed from R9C5
R8C6 has been set to <5>.
Possibility <2> removed from R6C7
R9C5 has been set to <1>.
R8C9 has been set to <1>.
R9C2 has been set to <3>.
R9C8 has been set to <8>.
R1C8 has been set to <3>.
R1C7 has been set to <8>.
R3C7 has been set to <2>.
R3C1 has been set to <6>.
R1C2 has been set to <2>.
R6C2 has been set to <6>.
R1C3 has been set to <7>.
R1C9 has been set to <6>.
R6C5 has been set to <5>.
R4C5 has been set to <6>.
R6C8 has been set to <1>.
R4C8 has been set to <5>.
R4C3 has been set to <2>.
R5C1 has been set to <5>.
R7C3 has been set to <6>.
R4C9 has been set to <7>.
R7C9 has been set to <3>.
R5C9 has been set to <2>.
R6C7 has been set to <3>.
R8C7 has been set to <6>.
R8C4 has been set to <3>.
R9C7 has been set to <7>.
R9C1 has been set to <2>.
R9C3 has been set to <5>.
R7C1 has been set to <7>.
R9C4 has been set to <6>.
R7C6 has been set to <2>.
R2C4 has been set to <7>.
R2C6 has been set to <6>.
R6C4 has been set to <2>.
R4C6 has been set to <1>.
R5C6 has been set to <3>.
R6C6 has been set to <7>.

The only unusual step was a remote pair to eliminate <2> in R6C7.

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Postby Pyrrhon » Sun May 07, 2006 4:54 pm

Sorry I misplaced a point. The sudoku in question is:

Code: Select all
...5.....
.5..2.19.
..9.38.7.
3.....4..
.71...96.
..4.....8
.1.89.5..
.98.7..2.
.....4... 
Pyrrhon
 
Posts: 240
Joined: 26 April 2006

Postby ravel » Sun May 07, 2006 8:20 pm

After counting the candidates in r4c9 to be 27 (and denoting some pairs before), it was easy with the 2 strong links (turbot fish) from the 26-pairs, that eliminate the 2. This gives a 7 and an x-wing in 2, which forces the 2 in r5c9.
Shortly: 2SL, x-wing

This seems to be the same solution as the one Keith has posted.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Viggo » Sun May 07, 2006 11:56 pm

After the first easy part I got:

7 Boxline eliminations revealing 18 singles
1 naked pair elimination
2 Turbot fish
1 Discontinuos nice loop w. 7 links

Then the puzzle collapsed.

/Viggo
Viggo
 
Posts: 60
Joined: 21 April 2006

Postby Pyrrhon » Mon May 08, 2006 10:16 am

Thank you for your input. Now the computer programs:

    Simple Sudoku: Naked Pair, X-Wing, Sowrdfish, Naked Pair, Colors

    Sudoku Susser: 2 Naked Pairs, 2 remote pairs

    SudoCue: Line-Box-Reduction, X-Wing, Jellyfish, Naked Pair, Colors

    Scanraid: can't solve it

Humans:

    Keith: box-line-interaction, nakedpair, remote pair

    ravel: Turbot fish, X-wing

    Viggo:7 line-box-reduction, naked pair, Turbot fish, 1 discontinous nice loop with 7 links

It seems that some observations can be made. It should be improved whether these are more general differences:

    Humans seems to have a more heuristical approach than a brute force wheather a special technique is useable, so for example Keith finds line-box intersections even if hidden single are available. I. e. if they see that there are many 26-cells than they check for techniques using these cells If a human player spots a strong link he is searching for a technique to use it, programs take a choice and look for the pattern after that.

    The programms find such interesting things like swordfish or jellyfish with there brute force check for the techniques, while humans find much simpler things like turbot fishs or remote pairs.

    Sudoku Susser is in this sudoku mostly near with Keith, Viggo and ravel.

    The simplest solution was found by Keith and not by one of the programs

    Human seem to find more line-box-interactions then programs do. This seems to be because the search for hidden subsets and line-box-interactions in one run. It should be improved whether programs should take this in account if the estimate the difficulty of a sudoku.

    No program has found a turbot fish but it seems that humans do. So programs should check this technique if they are searching for the difficulty of a sudoku (before x-wing, swordfish, jellyfish ...)


Are you agree? Have you other observations?

Pyrrhon
Pyrrhon
 
Posts: 240
Joined: 26 April 2006

Postby ravel » Mon May 08, 2006 12:00 pm

First a note to the programs:
They would work much more like humans, if the implementations would better reflect the order, in which the methods are ascending difficult to use for humans.
For historical reasons, i suppose, Simple Sudoku looks for swordfish before coloring, though 2 and often 3 strong links are easier to spot.
Same problem with susser: Accidently here the strong links are also remote pairs, so susser finds them early. Otherwise it would only detect them with nishio, which comes after a lot of more advanced techniques like forcing chains.
I dont know SudoCue, bit it seems that also here big fishes are before coloring.

So some minor improvements in the programs would lead to much more human-like results.

Then you have to consider, if one is using no pencil marks, only a few or all pm's in a given situation.
Without pm's box-line-interactions and even hidden pairs or some x-wings are easier to spot (with one/two glances) than some naked singles, where you have to count through the numbers.
On paper i only mark pairs, until i get stuck. Then i count the candidates for cells, where it looks that only a few candidates remain, to find naked singles and bivalue cells. Only when i am stuck again, i fill all candidates in.
Some people dont use any pm's, some fill them all in, when stuck the first time. When using a program, you can have them automatically from the beginning.
So this is a point, where also humans differ.
Another is, that the ones prefer patterns, the other chains. So one might see the swordfish, the other the 7-cell chain first.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby tarek » Mon May 08, 2006 10:25 pm

Tarek's solver
Code: Select all
Box-line interaction
XWing
2x2x3 Swordfish
Naked/Hidden double
Finned XWing

Tarek
User avatar
tarek
 
Posts: 2612
Joined: 05 January 2006

Postby Havard » Mon May 08, 2006 11:32 pm

Havard's solver:
Code: Select all
Box-Line:
1      26     7      | 5      4      9      | 8      3      26
8      5      3      | 67     2      67     | 1      9      4
26     4      9      | 1      3      8      | 26     7      5
---------------------+----------------------+---------------------
3      8      26     | 9      56X    1267-  | 4      15     27
5      7      1      | 4      8      23     | 9      6      23
9      26     4      | 2367-  56X    12367- | 237    15     8
---------------------+----------------------+---------------------
267    1      26     | 8      9      236    | 5      4      367
4      9      8      | 36     7      5      | 36     2      1
267    3      5      | 26     1      4      | 67     8      9

.  6  .  | .  .  .  | .  .  6
.  .  .  | 6  .  6  | .  .  .
6  .  .  | .  .  .  | 6  .  .
---------+----------+---------
.  .  6  | .  6X 6- | .  .  .
.  .  .  | .  .  .  | .  6  .
.  6  .  | 6- 6X 6- | .  .  .
---------+----------+---------
6  .  6  | .  .  6  | .  .  6
.  .  .  | 6  .  .  | 6  .  .
6  .  .  | 6  .  .  | 6  .  .


Skyscraper in columns: 2 7
1    26X  7    | 5    4    9    | 8    3    26-
8    5    3    | 67   2    67   | 1    9    4
26-  4    9    | 1    3    8    | 26X  7    5
---------------+----------------+---------------
3    8    26   | 9    56   127  | 4    15   27
5    7    1    | 4    8    23   | 9    6    23
9    26X  4    | 237  56   1237 | 237X 15   8
---------------+----------------+---------------
267  1    26   | 8    9    236  | 5    4    367
4    9    8    | 36   7    5    | 36   2    1
267  3    5    | 26   1    4    | 67   8    9

.  2X .  | .  .  .  | .  .  2-
.  .  .  | .  2  .  | .  .  .
2- .  .  | .  .  .  | 2X .  .
---------+----------+---------
.  .  2  | .  .  2  | .  .  2
.  .  .  | .  .  2  | .  .  2
.  2X .  | 2  .  2  | 2X .  .
---------+----------+---------
2  .  2  | .  .  2  | .  .  .
.  .  .  | .  .  .  | .  2  .
2  .  .  | 2  .  .  | .  .  .


Havard
Havard
 
Posts: 377
Joined: 25 December 2005

My comments

Postby keith » Tue May 09, 2006 1:26 am

I think I disagree a little with this:

The simplest solution was found by Keith and not by one of the programs


If you change the order of the heuristics in Sudoku Susser slightly, you will probably get my "simpler" solution. I think it depends on what you think the relative difficulty of "remote pairs" is.

It is no accident that my solution is closest to that given by Sudoku Susser. It is the program I use for learning.

I do agree with the comment that humans look for patterns and then for heuristics; Computer programs progress through some hierarchy of heuristics, and then analyze "all" patterns.

I was not looking for the "simplest" solution. In fact, I think that most of us enjoy using "advanced" techniques when simpler ones might apply.

Another interesting experiment might be to scramble the puzzle, and see what the humans (and the programs) do next time.

Best wishes,

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Simpler solutions? Remote Pairs vs Simple Colouring

Postby chrisr » Thu May 11, 2006 10:31 pm

keith wrote:I think I disagree a little with this:
If you change the order of the heuristics in Sudoku Susser slightly, you will probably get my "simpler" solution. I think it depends on what you think the relative difficulty of "remote pairs" is.


Is "remote pairs" related to 'simple colouring"? Because "simple colouring" was the only technique my solver program really needed to find a solution. Well, besides 3 locked candidates, that is.
chrisr
 
Posts: 11
Joined: 19 October 2005

Re: Simpler solutions? Remote Pairs vs Simple Colouring

Postby ravel » Thu May 11, 2006 11:12 pm

chrisr wrote:Is "remote pairs" related to 'simple colouring"? Because "simple colouring" was the only technique my solver program really needed to find a solution. Well, besides 3 locked candidates, that is.

Thought, this question was already answered, maybe elsewhere.
Remote pairs are an even number of connected pairs of candidates, e.g. 26-26-26-26, through different units (box, row, column). Then you can eliminate both of them from all cells, that both "see" (share a unit with) the beginning and the end of the chain.
So they are simple colouring chains for both of the candidates.
ravel
 
Posts: 998
Joined: 21 February 2006

Re: Simpler solutions? Remote Pairs vs Simple Colouring

Postby chrisr » Thu May 11, 2006 11:46 pm

ravel wrote:Remote pairs are an even number of connected pairs of candidates, e.g. 26-26-26-26, through different units (box, row, column). Then you can eliminate both of them from all cells, that both "see" (share a unit with) the beginning and the end of the chain.
So they are simple colouring chains for both of the candidates.


Hmm, that's something to get my head around. But I can't see how that's simpler than "simple colouring" in this case.
chrisr
 
Posts: 11
Joined: 19 October 2005

Next

Return to Advanced solving techniques