The weekend sudoku : comments [oldbloke's mutterings]

My program, and my brain, got to here:

[ 9 ][ 5 ][ 1 ][ 34 ][ 23 ][ 234 ][ 6 ][ 7 ][ 8 ]
[ 46 ][ 246 ][ 26 ][ 89 ][ 89 ][ 7 ][ 3 ][ 1 ][ 5 ]
[ 8 ][ 7 ][ 3 ][ 5 ][ 6 ][ 1 ][ 29 ][ 49 ][ 24 ]
[ 2 ][ 3 ][ 678 ][46789][ 1 ][ 4689][ 589 ][ 4589][ 46 ]
[ 4567][ 46 ][ 9 ][34678][23578][23468][ 1 ][ 458 ][ 246 ]
[ 456 ][ 1 ][ 68 ][ 4689][ 2589][24689][ 2589][ 3 ][ 7 ]
[ 3 ][ 26 ][ 267 ][ 1 ][ 4 ][ 5 ][ 78 ][ 68 ][ 9 ]
[ 1 ][ 9 ][ 4 ][ 2 ][ 78 ][ 68 ][ 57 ][ 56 ][ 3 ]
[ 67 ][ 8 ][ 5 ][ 3679][ 379 ][ 369 ][ 4 ][ 2 ][ 1 ]

From here, choosing to put either a 6 or 7 in the bottom left cell leads to a solution.
Unless I made an error somewhere, of course.
Will your program tell you what it's done at each point?

[parent entry] [link] [parent] [reply]

damned html 2spaces-are-1 thang!

[link] [parent] [reply]

Unfortunately it's not really possible to find out what my program did on the way - I wrote it in ML, so it's all about recursive operations on lists. You start out with a list containing a single soduku with 1 to 9 in each box (except for the values we already know of course), and it finds the first box with more than one number, and makes a new soduko for each possibility, removes the chosen number from the rest of its row, column and square, and then throws away the sudoku it doesn't "work" (i.e. results in an empty box somewhere). It then takes every new soduko puzzle in the list and repeats the above, and eventually you should end up with "all" possible solutions, which is hopefuly just the one unique solution. Unfortunately this (presumably) means the number of sudokus increases dramatically at the start before reducing down to the correct solution, so a mid-point wouldn't tell you much.

[link] [parent] [reply]

Ah.
I did mine in Perl, deliberately attacking it "the way a human would" - except it does the exhaustive "only 1 candidate works here" check first as it's so easy for a computer, where a human doesn't as it's not immediately visible. We tend to start with what in my prog are the 3rd and 4th checking algorithms.
I always wondered if my prog couldn't do that sudoku because I never programmed the last 3 algorithms I found on the web, or never extended some of the earlier ones to candidate sets bigger than 3.
Can you put 'the point I got stuck at' into your prog?

[link] [parent] [reply]

and also maybe 'the point i got stuck at' + making the bottom left a 6 [or 7]

[link] [parent] [reply]

Right, I tried this - with the puzzle above (well, actually it was the puzzle with 1 to 9 in each cell, then for each single number I bunged that in, and it removes that number from each row, column, square, leaving much the same puzzle as you have above, bar just a few cells with a couple of extra numbers in it), it gave the single answer I give above; with 6 in the bottom left, it reckoned no answer; with 7 in the bottom left, answer above again.

I just tried it by hand, as well - the version with a 6 bottom left that is - and eventually ended up with a 9 in both the top right and bottom left of the centre square; but it was a slapdash enough attempt I may well have gone wrong somewhere.

[link] [parent] [reply]

Yep, I'll bung it in tonight (the prog is on my home computer).

I deliberately went the other way and attacked it by pure brute force, as I was curious to see whether it would run out of time/memory, but it seems to zap through them all with no trouble. I ought to put something in to find out how many sodukos it end up with at different stages, really.

[link] [parent] [reply]

I agree with those numbers, except I had fewer 5s in the middle right-hand block because it's known that the 5 has to go on the top row.

However, I tried putting 6 in the bottom left cell and it ended up in a contradiction (and I tried it twice), so I suggest you check your solution. :-)

[link] [parent] [reply]

ah... I'll check that again, then.

[link] [parent] [reply]

So the question now is, what logical deduction can you make from "the point where I got stuck" to tell you that bottom left is a 7 - or that the 6 leads to a failure. And I want it to be something you can hold in your head!
I didn't see any XYwing formations, but I'm not adept at spotting them.
If it's a Forcing Chain, Colouring, or Nishio, how long is the required inference chain? Can it reasonably be done in your head?

[link] [parent] [reply]

Can it reasonably be done in your head?

Not in my head, no. But I'm not a sudoku expert.

[link] [parent] [reply]

Sun	Mon	Tue	Wed	Thu	Fri	Sat
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29 1	30	31

oldbloke's mutterings

(no subject)

(no subject)

(no subject)

(no subject)

(no subject)

(no subject)

(no subject)

(no subject)

(no subject)

(no subject)

(no subject)

May