The weekend sudoku

[oldbloke]

Graun hard nothing special, as per.
Graun killer didn't need too much back-of-envelope this week, quite pleasant.
Took 3 goes at the Indy hex, tsk, stupid mistakes each time.
Seem to have forgotten to do the futoshiki...

This bit has been elsewhere on LJ recently:
Soem time ago there was a sudoku in the Graun I couldn't do.
Had another look at it last week. At the point I got stuck, there was a cell with only two candidates, so I made two copies and worked through each possibility. Both lead to "solutions". Not unique. Tsk.

Just got a -10 on the crazy golf.

Comments

[anshackles.livejournal.com]

Do they actually *have* to have unique solutions? or is it acceptable to have one with more then one solution?

[oldbloke.livejournal.com]

Well... If there are multiple "solution"s, you're bound to reach a point where you can't decide what's in some cell - because several things are valid. So how do you finish it?

[muffledsqueak.livejournal.com]

Could you show us the two-solution soduko please?

[oldbloke.livejournal.com]

0s are empty cells

950000670
000007310
800561000
230000000
009000100
000000037
000145009
094200000
085000021

There's an LJ thread somewhere with one that has (iirc) 3 "solutions"

[imc.livejournal.com]

YM "at least 3 solutions", as it probably actually has dozens.

[muffledsqueak.livejournal.com]

Hmm ... I wanted to stuck this through the sudoku program I made, because I wanted to try it out on a problem that had multiple solutions (and I've only been able to think of puzzles that have hundreds of solutions, and it takes too long thinking about it); but it claims there is only one solution:

[[9]; [5]; [1]; [3]; [2]; [4]; [6]; [7]; [8]];
[[6]; [4]; [2]; [8]; [9]; [7]; [3]; [1]; [5]];
[[8]; [7]; [3]; [5]; [6]; [1]; [2]; [9]; [4]];
[[2]; [3]; [7]; [4]; [1]; [9]; [8]; [5]; [6]];
[[5]; [6]; [9]; [7]; [8]; [3]; [1]; [4]; [2]];
[[4]; [1]; [8]; [6]; [5]; [2]; [9]; [3]; [7]];
[[3]; [2]; [6]; [1]; [4]; [5]; [7]; [8]; [9]];
[[1]; [9]; [4]; [2]; [7]; [8]; [5]; [6]; [3]];
[[7]; [8]; [5]; [9]; [3]; [6]; [4]; [2]; [1]]

Do both yours definitely fit?

[muffledsqueak.livejournal.com]

Oh, incidentally, don't feel you have to waste your time on this if you have better things to do.

[oldbloke.livejournal.com]

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?

[oldbloke.livejournal.com]

damned html 2spaces-are-1 thang!

[muffledsqueak.livejournal.com]

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.

[oldbloke.livejournal.com]

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?

[oldbloke.livejournal.com]

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

[muffledsqueak.livejournal.com]

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.

[muffledsqueak.livejournal.com]

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.

[imc.livejournal.com]

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. :-)

[oldbloke.livejournal.com]

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

[oldbloke.livejournal.com]

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?

[imc.livejournal.com]

Can it reasonably be done in your head?

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

[imc.livejournal.com]

If you fancy giving your proggy a run for its money, see if it can tell us how many solutions the aforementioned multi-valued sudoku has.

[muffledsqueak.livejournal.com]

Thanks! I'll give it a go tonight.

[muffledsqueak.livejournal.com]

Incidentally, I've seen a lot of people saying you should be able to do sudokus "logically", without guessing; although I can kind of see what they mean, this doesn't make much sense to me. For example, the rule whereby you have (say) two boxes in a row containing 1 and 2, so you know "by logic" that no other boxes in that row can contain 1 and 2; essentially what you're doing here seeing that if you guessed 1 or 2 for any of the other boxes, you would get an empty box, so those guesses can't be right. The "logic" people are talking about is just guesswork thatit happens to be easy for people to spot without needing to write stuff down.

[muffledsqueak.livejournal.com]

Ugh, typos aplenty there, sorry.

[oldbloke.livejournal.com]

It's widely known (ie may be a myth) that humans have a 7 element stack for instant-access stuff. So maybe the limit on a reasoning chain of that sort should be 7 items.

[muffledsqueak.livejournal.com]

4026, apparently.

[imc.livejournal.com]

Wow, that's a lot!