Sudoku

[K.I.L.E.R]

Thanks Simon.

 

[Simon F]

This is good to know. My paper just started with these puzzles, and my rudimentary solver kept solving them day after day. I was beginning to doubt if it's even possible to design a solvable puzzle that required insight/backtracking/permuting, but this nulls those doubts

Try these: They are the two "more challenging" ones that came from the Independent:

EDIT: Deleted the first one because I've missed out a clue or two!!!

		"57   6   ",
		" 2  74 1 ",
		"4  8     ",

		"  568 492",
		"      78 ",
		"   2 3   ",

		"     5127",
		"13 9     ",
		"       6 "

 

[Basic]

The first one doesn't seem to be a "real" Sudoku.

 

[Simon F]

The first one doesn't seem to be a "real" Sudoku.

Sorry, yes I'd just realised that .. I think I accidentally deleted one or two of the clues whilst editing the file/debugging. As it currently stands, it has several solutions.

 

[Simon F]

A "killer" for "k.i.l.e.r"

I just saw in the "The Times" that they have a new twist on Sudoku which goes by the, amusingly coincidental, title "Killer".

In this variant there are far fewer numbers written in (sometimes none at all!), but all squares are grouped into small contiguous regions (often similar to Tetris shapes). Each of these little regions is marked with the total sum of all values that it should contain.

Ahh just found an online version

Oh... and Mintmaster, I just realised that there are some less-likely tests I could apply to my solver before resorting to a recursive trial. It's a generalisation of the obvious basic rule that if a square only has one candidate it must contain that value and all others have it removed.

If you have a subset of N empty places in a row, column or square, all of which have exactly the same candidate set and there are also N things in that set, then those N can be removed from the candidate sets of all other places in the row/column/square.​

The thing is, it's probably more costly to code that up than go into a recursive search, so I haven't bothered (as yet). It is occasionally useful when solving by hand though.

 

[Frederik21]

I made an applet a while ago, that uses several strategies in each recursive loop, deleting impossible candidates from all the fields and filling in the fields that only have one valid candidate left.

It both solves and generates sudokus, except for the ones that require exceptionally rare solving techniques (not implemented as of yet).

It's not a very fast application, though better than some I've sen on the net. Actually, I think it's a good assignment, because the task isn't as trivial as it may seem. The generator works by repeatedly calling the solving algorithms to check out the validity of placed numbers. The numbers (1 through 9) are placed in sets of their value, because filling in the grid from top to bottom took ages. Kind of like the 8 queens problem, but with a lot more interdependent constraints.

Check out the applet if you like

http://sudoku.netgubbi.dk

 

[Simon F]

The generator works by repeatedly calling the solving algorithms to check out the validity of placed numbers. The numbers (1 through 9) are placed in sets of their value, because filling in the grid from top to bottom took ages.

I would have thought generating a puzzle would be, well, fairly straightforward... but perhaps I'm being naiive.
I would start by generating the complete solution - begin with, say, the top left 3x3 and fill in the 9 values randomly. Move one 3x3 to the right and fill in its elements, but obey the rules to the left. Continue on etc etc.

Alternatively, start with a known solved puzzle and swap whole 3x rows or 3x columns OR single rows or columns with one of their neighbours in the set of 3, and also remap the 1..9 values into a different combination.


Then to make it a puzzle, remove some number of elements and see if you can solve it, if not put some back in (binary chop I guess), till you get to the bare minimum needed to get a unique solution. Then just add some number to change the difficulty level.

 

[OpenGL guy]

A good site for puzzles that are a bit more challenging than the usual newspaper-Sudoku is:
http://www.paulspages.co.uk/sudoku/index.htm
You can either generate new Sudoku with various difficulty levels, or pick one from the gallery. The gallery has a "outlaw" section with Sudoku that need testing and back-tracking.

Thanks for the link. I just tried one of the "Really Tough" puzzles and solved it in about 6 minutes. I'll give the outlaw ones a try later.

I picked up a book of Su Doku puzzles but wasn't impressed by the difficulty at all.

Edit: Oops, it wasn't a really tough one. I'll get back to you later

 

[K.I.L.E.R]

I would like to let you guys know that my GA has been finished for 2 weeks.

I left it on for 5 hours yesterday and it hasn't solved it.
It does come quite close to solving it however.

 

[Simon F]

I would like to let you guys know that my GA has been finished for 2 weeks.

I left it on for 5 hours yesterday and it hasn't solved it.
It does come quite close to solving it however.

Doesn't that tell you something about your choice of algorithm.......

The simple C program I wrote solves them in sub-millisecond time (and it's not optimised - but why would one bother? ).

 

[Simon F]

The numbers (1 through 9) are placed in sets of their value, because filling in the grid from top to bottom took ages. Kind of like the 8 queens problem, but with a lot more interdependent constraints.

More like the "8 rooks problem". This is actually quite relevant to 3D graphics because it's used as a method to place supersampling points for AA.


As for your app - what would be nice is being able to mark the possibles/impossibles. Either have lists associated with (and adjacent to) each row/column/ 3x3 giving theremaining entries. Alternatively, put a small 3x3 grid inside each square. The user can then mark each impossible candidate by shading in the corresponding sub-square (sort of like noughts-and-crosses (aka tic-tac-toe)) (You could make it partially automatic if you wanted to)

 

[DemoCoder]

I would like to let you guys know that my GA has been finished for 2 weeks.

I left it on for 5 hours yesterday and it hasn't solved it.
It does come quite close to solving it however.

Keep in mind that GA can't solve all problems.

 

[K.I.L.E.R]

It's using a GA.
A GA is THE worst algorithm you could possibly use to solve this.
By the time I get a good answer, it sure as hell doesn't stay there for a long time.

Since Sudoku puzzles have only a single solution it is not practical to attempt to lock genes/squares and GAs don't backtrack.

Doesn't that tell you something about your choice of algorithm.......

The simple C program I wrote solves them in sub-millisecond time (and it's not optimised - but why would one bother? ).

 

[Frederik21]

Hey Simon - thanks for the feedback

As for the numbering of candidates, I know a lot of people use this, but I never did and I think it clutters the application too much - more of a stylistic decision than anything else. I have made some updates to my site ( http://sudoku.netgubbi.dk ) so now there are multiple difficulty levels and more advanced feedback from the buttons. The check button can be used to provide indirect hints and so.

The creation method you mention is what I tried out first, but it generates probems that calls for massive backtracking (slowing down the app), because placing the numbers in that way doesn't take into consideration that legally placed numbers can block the possible position of other numbers later on. You may actually fill in almost the entire board legally, and then come to a dead end (no possible candidates for next field) and you will have to backtrack many steps and rearrange - that's the interdependent constraints I talked about. Of course, if you're a shark at optimizing your code (as it seems), this may be no problem at all, but I decided on the other way because it worked for me.

Btw. I think 8 queens is a better metaphore than 8 rooks - the constraints in soduko are in three dimensions (like a queen moves along 3 axis), not 2 like a rook.

 

[Simon F]

Hey Simon - thanks for the feedback

As for the numbering of candidates, I know a lot of people use this, but I never did and I think it clutters the application too much - more of a stylistic decision than anything else.

In that case, could you at least allow letters or other symbols to be entered in? It's nice to be able to make notes and it's rather difficult to do that without either printing the page OR writing all over the screen

The creation method you mention is what I tried out first, but it generates probems that calls for massive backtracking (slowing down the app), because placing the numbers in that way doesn't take into consideration that legally placed numbers can block the possible position of other numbers later on.

I'll have to test this... I'll hack my program at lunchtime to see how long it takes from a "nearly blank" board.

You may actually fill in almost the entire board legally, and then come to a dead end (no possible candidates for next field) and you will have to backtrack many steps and rearrange

When my solver resorts to recursion, I always start with the square with the fewest candidates - do you use that approach?