|
| View previous topic :: View next topic |
| Author |
Message |
| Tempbow
| | Joined: 18 Apr 2005 | | Posts: 22 | | : | |
Items |
|
 Posted: Tue Apr 26, 2005 8:50 am Post subject: Difficult Problems |
 |
|
The following puzzle is solvable by making a guess in column 2.
I am looking for a logic method that my program obviously lacks.
NOTE: the puzzle is blank in column 1 and 9.
Cut and paste this:
| Code: | 8 3 6
3 1
975 38
9 2
8 7 4
3 6
16 289
49 2
521 964 |
| Code: | +---+---+---+
| 8 | 3| 6 |
| 3 | | 1 |
| 97|5 |38 |
+---+---+---+
| | 9 |2 |
| 8| 7 |4 |
| 3| 6 | |
+---+---+---+
| 16| 2|89 |
| 49| | 2 |
| 52|1 9|64 |
+---+---+---+ |
POSSIBLE ENTRIES:
| Code: | 1245 8 145 479 124 3 579 6 24579
2456 3 45 46789 248 4678 579 1 24579
1246 9 7 5 124 46 3 8 24
145 67 145 348 9 1458 2 357 168
159 26 8 23 7 15 4 35 169
1459 27 3 248 6 1458 19 57 189
37 1 6 47 345 2 8 9 357
378 4 9 678 358 678 157 2 1357
378 5 2 1 38 9 6 4 37 |
=====
Target is 81, solved: 31 possibles count: 180 |
|
| Back to top |
|
 |
| Tempbow
| | Joined: 18 Apr 2005 | | Posts: 22 | | : | |
Items |
|
| Posted: Tue Apr 26, 2005 8:53 am Post subject: |
|
|
This is another that I would like some tips on. I have tried the algorithms including N-tuples, Xwing, Swordfish etc, but the problem is not reduced any further.
| Code: | +---+---+---+
| 6| | 37|
| 93|7 | 21|
|257|138|469|
+---+---+---+
|3 9| |754|
| 8|9 5|213|
|5 1| |986|
+---+---+---+
| 35|247| 98|
|782| | 45|
|9 4| |372|
+---+---+---+ |
POSSIBLE ENTRIES:
| Code: | 148 14 6 45 29 29 58 3 7
48 9 3 7 56 46 58 2 1
2 5 7 1 3 8 4 6 9
3 26 9 68 1268 126 7 5 4
46 467 8 9 67 5 2 1 3
5 27 1 34 27 34 9 8 6
16 3 5 2 4 7 16 9 8
7 8 2 36 169 1369 16 4 5
9 16 4 58 58 16 3 7 2 |
=====
Target is 81, solved: 50 poss count: 120
State tables:
| Code: | +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
|11.|...|...| |...|.22|...| |...|...|.*.| |44.|4..|...| |...|5..|5..|
|...|...|..*| |...|...|.*.| |..*|...|...| |4..|..4|...| |...|.5.|5..|
|...|*..|...| |*..|...|...| |...|.*.|...| |...|...|*..| |.*.|...|...|
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
|...|.11|...| |.2.|.22|...| |*..|...|...| |...|...|..*| |...|...|.*.|
|...|...|.*.| |...|...|*..| |...|...|..*| |44.|...|...| |...|..*|...|
|..*|...|...| |.2.|.2.|...| |...|3.3|...| |...|4.4|...| |*..|...|...|
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
|1..|...|1..| |...|*..|...| |.*.|...|...| |...|.*.|...| |..*|...|...|
|...|.11|1..| |..*|...|...| |...|3.3|...| |...|...|.*.| |...|...|..*|
|.1.|..1|...| |...|...|..*| |...|...|*..| |..*|...|...| |...|55.|...|
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
|..*|...|...| |...|...|..*| |8..|...|8..| |...|.99|...|
|...|.66|...| |...|*..|...| |8..|...|8..| |.*.|...|...|
|...|...|.*.| |..*|...|...| |...|..*|...| |...|...|..*|
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
|.6.|666|...| |...|...|*..| |...|88.|...| |..*|...|...|
|66.|.6.|...| |.7.|.7.|...| |..*|...|...| |...|*..|...|
|...|...|..*| |.7.|.7.|...| |...|...|.*.| |...|...|*..|
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
|6..|...|6..| |...|..*|...| |...|...|..*| |...|...|.*.|
|...|666|6..| |*..|...|...| |.*.|...|...| |...|.99|...|
|.6.|..6|...| |...|...|.*.| |...|88.|...| |*..|...|...|
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |
|
|
| Back to top |
|
|
| rubylips
| | Joined: 07 Apr 2005 | | Posts: 62 | | : | | Location: London |
Items |
|
| Posted: Tue Apr 26, 2005 9:53 am Post subject: |
|
|
The first puzzle has been taken from the 'Setting Sudoku' forum. As I state in that forum, I don't know of any logical manner in which to solve the puzzle (which isn't to say that no such manner exists - it's just highly unlikely). The main, perhaps sole, purpose of the puzzle is to test the performance of guess-based solvers.
With regard to the second puzzle, my solver finds a Nishio that allows the puzzle to be solved without a guess - though some would consider a Nishio to be a guess. Here's the solver output:
| Quote: | The value 4 in Box [2,1] must lie in Row 5.
The values 2 and 9 occupy the cells (1,5) and (1,6) in some order.
The values 3 and 4 occupy the cells (6,4) and (6,6) in some order.
The values 5 and 8 occupy the cells (9,4) and (9,5) in some order.
The move (4,2):= 6 would make it impossible to place the remaining 6s.
The value 2 is the only candidate for the cell (4,2). |
Read more about Nishio in the 'Solving sudoku' forum. |
|
| Back to top |
|
|
| Tempbow
| | Joined: 18 Apr 2005 | | Posts: 22 | | : | |
Items |
|
| Posted: Tue Apr 26, 2005 11:57 am Post subject: |
|
|
| rubylips wrote: | | The first puzzle has been taken from the 'Setting Sudoku' forum. As I state in that forum, I don't know of any logical manner in which to solve the puzzle (which isn't to say that no such manner exists - it's just highly unlikely). The main, perhaps sole, purpose of the puzzle is to test the performance of guess-based solvers. |
Yes, that is why I have posted it. I am working with puzzles that my program fails to solve, in the belief that there should be some more logic other than trial and error.
| rubylips wrote: | With regard to the second puzzle, my solver finds a Nishio that allows the puzzle to be solved without a guess - though some would consider a Nishio to be a guess. Here's the solver output:
The value 4 in Box [2,1] must lie in Row 5.
The values 2 and 9 occupy the cells (1,5) and (1,6) in some order.
The values 3 and 4 occupy the cells (6,4) and (6,6) in some order.
The values 5 and 8 occupy the cells (9,4) and (9,5) in some order.
The move (4,2):= 6 would make it impossible to place the remaining 6s.
The value 2 is the only candidate for the cell (4,2).
Read more about Nishio in the 'Solving sudoku' forum. |
I do not see the relevance to the Nishio implementation of
| Quote: | The value 4 in Box [2,1] must lie in Row 5.
The values 2 and 9 occupy the cells (1,5) and (1,6) in some order.
The values 3 and 4 occupy the cells (6,4) and (6,6) in some order.
The values 5 and 8 occupy the cells (9,4) and (9,5) in some order. |
Am I right in assuming that it is unrelated, and documents the discovery of 2-tuples that may have been useful to make further reductions?
Nor do I see the logic behind the Nishio choice of cell (4,2) | Quote: | | The move (4,2):= 6 |
But given that that is the selection, I can readily see the status table for p=6 devolving into:
| Code: | +---+---+---+
|..*|...|...|
|...|..6|...|
|...|...|.*.|
+---+---+---+
|.*.|...|...|
|...|.6.|...|
|...|...|..*|
+---+---+---+
|6..|...|6..|
|...|6..|6..|
|...|...|...|
+---+---+---+ |
This clearly has "no room at the inn" for 6 in row 9, nor box 9, ruling it out as a choice. But as has been already agreed, Nishio falls into the T&E category of "try this, and see if it works - if not, unravel it and try another option". I have not elected to include Nishio in my program. Are you suggesting that there exists a rigorous proof that no other logic can be used other than a T&E approach? I have read the broad categorisation of type 1, type 2 and type 3 puzzles. I am theorising that - given a puzzle is set such that there can be only one solution given the initial clues, then there will exist a set of logic rules that will enable a solution without T&E.
But just as I can not provide a rigorous proof that in this case, no other logic can be used other than a T&E approach, so I can also not provide a rigorous proof of the theory there will exist a set of logic rules that will enable a solution without T&E. 
Maybe I should regard solving a Sudoku as analogous to playing chess. A player who adopts a strategy of considering the consequences of only one future move, is going to be a very limited player . . .  |
|
| Back to top |
|
|
| rubylips
| | Joined: 07 Apr 2005 | | Posts: 62 | | : | | Location: London |
Items |
|
| Posted: Tue Apr 26, 2005 1:06 pm Post subject: |
|
|
| Quote: | | Am I right in assuming that it is unrelated, and documents the discovery of 2-tuples that may have been useful to make further reductions? |
That's right. The default behaviour of my solver (http://act365.com/sudoku) is to apply the known elimination rules in the order (my names):Single Sector Candidates, Disjoint Subsets, X-Wings, Swordfish, Nishio and finally Guess until a definite move is found. Any rule that leads to the elimination of a candidate is printed out - however, as you state, it doesn't necessarily follow that an earlier rule in the list is a logical prerequisite for a later rule.
| Quote: | | Nor do I see the logic behind the Nishio choice of cell (4,2) |
That's because there isn't any! When Nishio is applied, it scans each remaining cell/value combination to see whether it would violate further progress (which makes the rule, relatively speaking, very slow to apply). It so happens in this case that just the one move (4,2):=6 has been eliminated.
| Quote: | | But as has been already agreed, Nishio falls into the T&E category of "try this, and see if it works - if not, unravel it and try another option". |
I don't disagree but I still think you should implement it - simply because Nishio is a very powerful tool for the discovery of new 'purely logical' patterns. Remember that X-Wings and Swordfish are simply special cases of Nishio. In some sense, Nishio highlights the 'most vulnerable' of the remaining candidates. I'm certain that the best way to find a new logically-assertive pattern in your position would be to consider the 6s around the cell (4,2).
| Quote: | | Are you suggesting that there exists a rigorous proof that no other logic can be used other than a T&E approach? |
No.
| Quote: | | I am theorising that - given a puzzle is set such that there can be only one solution given the initial clues, then there will exist a set of logic rules that will enable a solution without T&E. |
I would be delighted if this were the case but I suspect it isn't.
| Quote: | | Maybe I should regard solving a Sudoku as analogous to playing chess. A player who adopts a strategy of considering the consequences of only one future move, is going to be a very limited player . . . |
I don't even look that far ahead ...  |
|
| Back to top |
|
|
| Tempbow
| | Joined: 18 Apr 2005 | | Posts: 22 | | : | |
Items |
|
| Posted: Wed Apr 27, 2005 8:26 am Post subject: |
|
|
I concur with most of your posting. However, I would like to examine this statement in detail -
[quote="rubylips"] | Quote: | | ... Remember that X-Wings and Swordfish are simply special cases of Nishio. In some sense, Nishio highlights the 'most vulnerable' of the remaining candidates. |
Let's get right back to basics to see if that assertion holds water:
Let us start with a sudoku matrix, SU(r,c,p) dimensioned (9x9x9)
The first two dimensions (r,c) are the row and column number of each cell.
The third dimension contains the possible element that contends for that cell.
Each cell contains a state value. We could set the state value as
0 = not eligible for that possible (p)
1 = eligible for that possible
2 = known to contain that possible
So the proper initial state setting for all cells is 1
Before receiving a sudoku puzzle, all cells are initiated to that known state.
On accepting a sudoku puzzle, some cells can immediately be updated.
If row 5 column 5 contains a 9, then
SU(5,5,9) = 2 and SU(5,5,1) through SU(5,5,8) = 0
We can also immediately apply a uniqueness elimination rule, that this cell's row, column and box cannot contain a value of 9:
SU(5,1-4,9) & SU(5,6-9,9) = 0
SU(1-4,5,9) & SU(6-9,5,9) = 0
SU(4-6,4-6,9) = 0 except SU(5,5,9) which = 2
SU(r,c,9) can be seen to contain
| Code: | 111101111
111101111
111101111
111101111
000020000
111101111
111101111
111101111 |
Let us now examine an XWING.
Suppose that the only places that a 6 can be located for rows 1 and 9
are in the first and last cell. Since there is no statement concerning
rows 2 to 8, I will denote their contents as "?". SU(r,c,6) can be
seen to contain
| Code: | 100000001
?????????
?????????
?????????
?????????
?????????
?????????
?????????
100000001 |
Logic tells us that 6 will be in (1,1) and (9,9), or else (1,9) and (9,1).
In either case, there can not be a 6 in column 1 between the 2nd and 8th rows.
The same goes for column 9.
In this strategy, there is no question about trial and error. It is a straight
deduction. We do not have to place a 6 in either position to deduce the
SU(r,c,6) pattern
| Code: | 100000001
0???????0
0???????0
0???????0
0???????0
0???????0
0???????0
0???????0
100000001 |
That is why I can not accept your assertion quoted above. Your request that I remember your assertion as a fact, does not make it one!
Hence I accept Xwing and Swordfish as logic strategies, but I categorise Nishio as trial and error. Instead of categorising them as "simply special cases of Nishio", I would categorise them as "more general cases of uniqueness elimination". That is where we differ.
Terry (NZ) |
|
| Back to top |
|
|
| rubylips
| | Joined: 07 Apr 2005 | | Posts: 62 | | : | | Location: London |
Items |
|
| Posted: Wed Apr 27, 2005 11:40 am Post subject: |
|
|
| I agree that X-Wings and Swordfish are 'logical' (i.e. they use proof by assertion) whereas Nishio uses T & E (i.e. proof by contradiction) - however, this statement does not contradict my original assertion that X-Wings is a special case of Swordfish (where the 'wings' have unit length), which is itself a special case of Nishio (in the sense that any elimination made by Swordfish would also have been made by Nishio). |
|
| Back to top |
|
|
| tannedblondbloke
| | Joined: 18 Apr 2005 | | Posts: 2 | | : | |
Items |
|
| Posted: Thu Apr 28, 2005 6:26 am Post subject: |
|
|
| Tempbow wrote: |
This clearly has "no room at the inn" for 6 in row 9, nor box 9, ruling it out as a choice. But as has been already agreed, Nishio falls into the T&E category of "try this, and see if it works - if not, unravel it and try another option". I have not elected to include Nishio in my program. Are you suggesting that there exists a rigorous proof that no other logic can be used other than a T&E approach? I have read the broad categorisation of type 1, type 2 and type 3 puzzles. I am theorising that - given a puzzle is set such that there can be only one solution given the initial clues, then there will exist a set of logic rules that will enable a solution without T&E.
|
Types 1, 2 and 3? What's that?
_________________
Tanned Blond Bloke
London |
|
| Back to top |
|
|
| rubylips
| | Joined: 07 Apr 2005 | | Posts: 62 | | : | | Location: London |
Items |
|
| Posted: Thu Apr 28, 2005 8:01 am Post subject: |
|
|
I think Tempbow refers to the following post, made by Andrew McKernan to the Nishio thread on the old Google Groups 'Sudoku Programmers' forum:
| Quote: | My taxonomy of puzzle and solution types is 3-level
1. puzzles that can be solved by hand (even the "fiendish" puzzles fail to
register on my 10mS timer)
2. puzzles that can be solved by complex, zero-lookahead, analytical rules
3. puzzle that cannot be solved by any known rules and require recursive
tree-searching |
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
