A few new possibly interesting puzzles...

Everything about Sudoku that doesn't fit in one of the other sections

A few new possibly interesting puzzles...

Postby gfroyle » Fri Jun 24, 2005 6:47 am

Here are a few puzzles, all based on the same pattern...

Try them out and let me know what you think of them from a Sudoku players perspective... I like thinking about the mathematical aspects of Sudoku, but am not a really strong player myself..

http://www.csse.uwa.edu.au/~gordon/sudokupat.php

Cheers

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Re: A few new possibly interesting puzzles...

Postby angusj » Fri Jun 24, 2005 8:36 am

gfroyle wrote:Here are a few puzzles, all based on the same pattern...

Nice pattern. However, the only one I was able to solve in your X-Shape family without trial and error was No 3 - but it was a goody in that one step was a challenge:) .

I could solve all the 17-Hint and the 3 or 4 I tried in the Squares families too.

Edit: Looking at your website, it appears they appoint very young associate heads of departments over there in Perth:D
angusj
 
Posts: 306
Joined: 12 June 2005

Postby Nick70 » Fri Jun 24, 2005 10:17 am

They are all very hard, some even from the very first moves.

This is the only one that at the moment I can consider solvable without trial & error, but it's still very hard (the common techniques will not be enough):

Code: Select all
9...2...1
.8.....3.
..6...5..
...3.5...
8...6...9
...1.8...
..3...6..
.4.....5.
1...7...8


I'm curious, how are you generating these once you have chosen the pattern? Are you trying all possible combinations of clues, or putting them in at random?

I'm currently trying to enumerate and classify all possible problems for a 21-clues symmetric pattern I chose at random. I've generated about 13000 different problems so far, and I've explored only a fraction of the possible combinations.

Of the ~13000 problems, 31 could be reduced to 20 clues by removing the center cell, while 9 could be reduced to 19 clues by removing two symmetrically placed cells (always the same ones).

The following two are the hardest of the 19-clues problems I found so far. They can both be solved without trial & error.

Code: Select all
....2.7.5
.386.....
4........
.....5...
..2.1.6..
...4.....
........4
.....712.
8.9.5....


....9.8.7
.326.....
5........
.....5...
..8.1.3..
...4.....
........5
.....762.
8.1.3....
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby angusj » Fri Jun 24, 2005 12:24 pm

Nick70 wrote:The following two are the hardest of the 19-clues problems I found so far. They can both be solved without trial & error.

You've got me stumped on both of them (ie without t&e).
angusj
 
Posts: 306
Joined: 12 June 2005

Postby gfroyle » Fri Jun 24, 2005 12:33 pm

Nick70 wrote:This is the only one that at the moment I can consider solvable without trial & error, but it's still very hard (the common techniques will not be enough):


I have put another 14 of the same pattern (I will stop there) on the same page, but as has previously been mentioned, I don't know a precise enough definition of trial-and-error to say anything about that.

Nick70 wrote:I'm curious, how are you generating these once you have chosen the pattern? Are you trying all possible combinations of clues, or putting them in at random?


At the moment, I am generating at random from a starting pattern. Nothing incredibly clever - simply go through each position in some (specified, but arbitrary) order, and choose at random between the obviously feasible candidate entries. Then try to determine whether the resulting grid has 0, 1 or >1 completions, and keep only those with exactly one.

Exhaustive search through the space for even a single pattern would take a long time, though being smart about eliminating equivalence might make it feasible... must think about it some more.

Cheers

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby angusj » Fri Jun 24, 2005 1:50 pm

gfroyle wrote:I have put another 14 of the same pattern (I will stop there) on the same page, but as has previously been mentioned, I don't know a precise enough definition of trial-and-error to say anything about that.

The solving steps described here are the benchmark by which I judge what's currently 'easily applied logic' vs trial and error / proof by contradiction.

The only X-shaped puzzle that is doable (including your 14 new puzzles) based on the steps mentioned in my link above is No 3.
angusj
 
Posts: 306
Joined: 12 June 2005

Postby gfroyle » Sat Jun 25, 2005 1:20 am

angusj wrote:The solving steps described here are the benchmark by which I judge what's currently 'easily applied logic' vs trial and error / proof by contradiction.


Very interesting.. also a nice page, and nice looking program.. just need a MacOS or Linux version though as I don't have any Windows machines..

Cheers

gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby Nick70 » Sat Jun 25, 2005 10:19 am

angusj wrote:
Nick70 wrote:The following two are the hardest of the 19-clues problems I found so far. They can both be solved without trial & error.

You've got me stumped on both of them (ie without t&e).


Eh. I said they can be solved without t&e, but not that it would be easy:) It requires advanced coloring.
Let's take the first problem; I assume you would get stuck here:

Code: Select all
1      9      6      38     2      4      7      38     5
5      3      8      6      7      19     4      19     2
4      2      7      5      389    1389   89     13689  13689
67     18     4      2      3689   5      89     13789  13789
9      5      2      7      1      38     6      4      38
67     18     3      4      689    689    2      5      1789
2      7      1      389    368    368    5      89     4
3      6      5      89     4      7      1      2      89
8      4      9      1      5      2      3      67     67


look at these two forced chains:
(1,8)=8 -> A
(1,4)=8 -> B
(1,4)=3 -> A
(7,4)=3 -> B

(7,4)=9 -> C
(7,8)=9 -> D
(7,8)=8 -> C

now:
(7,8)=8 and (1,8)=8 exclude each other, so A and C cannot be true at the same time.
(7,4)=3 and (7,4)=9 exclude each other, so B and C cannot be true at the same time.

since both A and B exclude C, C must be false and D true. Therefore (7,8)=9.
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby angusj » Sat Jun 25, 2005 12:08 pm

Nick70 wrote:Eh. I said they can be solved without t&e, but not that it would be easy:)

So you did:) .

Nick70 wrote:Therefore (7,8)=9.

Yes, very well done.

However, isn't this really another (very clever) way of solving using proof by contradiction, where using colors in this way is just another way of testing one hypothesis? Anyhow, I'm not trying to argue your solution is invalid.
angusj
 
Posts: 306
Joined: 12 June 2005

Re: A few new possibly interesting puzzles...

Postby gabigabi » Sat Jun 25, 2005 3:26 pm

gfroyle wrote:Here are a few puzzles, all based on the same pattern...

Try them out and let me know what you think of them from a Sudoku players perspective... I like thinking about the mathematical aspects of Sudoku, but am not a really strong player myself..

http://www.csse.uwa.edu.au/~gordon/sudokupat.php

Cheers

Gordon
:D
gabigabi
 
Posts: 1
Joined: 25 June 2005

Re: A few new possibly interesting puzzles...

Postby VegHeadMoby » Sat Jun 25, 2005 3:40 pm

angusj wrote:Nice pattern. However, the only one I was able to solve in your X-Shape family without trial and error was No 3 - but it was a goody in that one step was a challenge:) .



Would anyone care to illuminate how to solve Gordon's X-Shape Puzzle #3 without using trial and error (and preferably with just a hint as to the method and not the entire solution)?

Thank you very much,

Emily
VegHeadMoby
 
Posts: 11
Joined: 25 June 2005

Re: A few new possibly interesting puzzles...

Postby angusj » Sat Jun 25, 2005 11:05 pm

VegHeadMoby wrote:Would anyone care to illuminate how to solve Gordon's X-Shape Puzzle #3 without using trial and error (and preferably with just a hint as to the method and not the entire solution)?

Hi Emily. When you get stuck try using colors.
angusj
 
Posts: 306
Joined: 12 June 2005

Postby VegHeadMoby » Mon Jun 27, 2005 4:04 am

:DThank you very much!

That was just enough of a hint to help solve the puzzle without giving anything away...
VegHeadMoby
 
Posts: 11
Joined: 25 June 2005

Postby little Zivvy » Mon Jun 27, 2005 10:55 pm

Indeed Puzzle 3 is excellent. Many thanks.

Can someone take a little trouble to explain the key step in this puzzle (which if I'm correct, leads to deducing the number in the cell at r6c2, by eliminating first 7's then 2's) . I can only barely follow coloring, and this puzzle seems a very good example from which to learn properly (finally!).

For the 7's .. a chain runs from Box1 thru, Boxes 2,6,9 and 7 to finally force the colors into cells r4c2 and r6c3 in Box4. This allows me to LOGICALLY eliminate the 7s in cells r4c3 and r6c2.
How should this be notated? (Maybe a reason I can't follow coloring may be the notation is very hard to follow).

For the 2's .. they seem more difficult. Here goes. Again starting at Box1 (coloring cell r3c1 yellow and cell r2c3 red), I proceed thru Box 3 and Box 6.
However, now i'm not sure I make the correct step. I can only close the loop/chain by coloring cell r6c3 yellow. Is this correct?
It then seems to me I have to place a red color in Box 4 too. This can only go at cell r4c2 but doesn't close the loop/chain. But, this process does allow 2's to be eliminated from cells r3c3 and r6c2.

Would be grateful if someone could let me know if this is correct coloring.
little Zivvy
 
Posts: 7
Joined: 13 June 2005

Postby scrose » Mon Jun 27, 2005 11:54 pm

little Zivvy wrote:Would be grateful if someone could let me know if this is correct coloring.

I couldn't quite understand your chain in the 7's, but you do appear to be eliminating the correct candidate 7's. Here is my chain of conjugate pairs of 7's, cell-by-cell. (R=red, Y=yellow)

Code: Select all
r2c3 (R) r3c1 (Y)
         r3c1 (Y) r8c1 (R)
                  r8c1 (R) r7c2 (Y)
                           r7c2 (Y) r7c9 (R)
                                    r7c9 (R) r8c7 (Y)
                                             r8c7 (Y) r6c7 (R)
                                                      r6c7 (R) r4c9 (Y)

r2c3 (R) and r4c9 (Y) allow you to eliminate the candidate 7 from r4c3.
r6c7 (R) and r7c2 (Y) allow you to eliminate the candidate 7 from r6c2.

However, I found that forming this long chain in the 7's was useless because the eliminations didn't actually let me fill in any cells. By comparison, I found colouring the 2's much easier. Here is my chain of conjugate pairs of 2's.

Code: Select all
r2c3 (R) r2c7 (Y)
         r2c7 (Y) r3c8 (R)
                  r3c8 (R) r9c8 (Y)

r2c3 (R) and r9c8 (Y) allow you to eliminate the candidate 2 from r9c3. At this point I could proceed filling in cells.

I hope this explanation helped. (And I hope I got all my coordinates right, so as not to confuse anyone.)

Update: It took me a while, but I was able to verify that your elimination of the candidate 2 from r6c2 is correct.

So, continuing from where I was above, I have eliminated the candidate 2 from r9c3. The chain of conjugate pairs of 2's can be extended.

Code: Select all
r2c3 (R) r3c1 (Y)
         r3c1 (Y) r8c1 (R)
                  r8c1 (R) r7c2 (Y)

At this point we can use r2c7 (Y) and r8c1 (R) to eliminate the candidate 2 from r8c7. Extend the chain again.

Code: Select all
r9c8 (Y) r7c9 (R)
         r7c9 (R) r4c9 (Y)
                  r4c9 (Y) r6c7 (R)

Finally, we can use r6c7 (R) and r7c2 (Y) to eliminate the candidate 2 from r6c2.

So, in the end, your method is absolutely correct; it allows you to place a number in the cell r6c2. However, note that it is much easier to form a short chain of 2's to eliminate a candidate 2 in r9c3 and thereby fill in that cell.
scrose
 
Posts: 322
Joined: 31 May 2005

Next

Return to General

cron