2 approaches

psionman · Posted: Thu May 12, 2005 8:29 am Post subject: 2 approaches

Hi

After a (very) little while the challenge of solving the puzzles turned into the challenge of writing a program to solve the problems

I have two programs that do this. Originally written in VBA for Excel they transfer perfectly to VB

The first approach is what I called the analytical about (650 lines of code). I have reproduced the algorithms that I use in manual solutions. This has solved every puzzle thrown at it by the Times in less than a 1 second

The second I call the synthetic approach (about 150 lines of code). This is the sledge-hammer approach of guessing a square and if it leads to a contradiction trying again. This is bound to lead to a solution in all cases for valid puzzles. It takes about 2 seconds to solve the most 'Fiendish' puzzles which can take up to 700,000 guesses.

I am happy to share the pseudo or VB code with anyone that might be interested.

Jeff

Animator · Posted: Thu May 12, 2005 11:58 am Post subject:

The puzzles in the times are easy... they don't even feature x-wings...

Perhaps you should take a look at the Very hard puzzles of the sudoku generator (of http://www.sudoku.com )... but that only goes up to x-wing, which is not the end... after that there are still many patterns

psionman · Posted: Thu May 12, 2005 2:31 pm Post subject:

Hi Animator

Can you point me to a 'hard' puzzle on line that I can test my algorithms against? I love a challenge Wink

Animator · Posted: Thu May 12, 2005 9:16 pm Post subject:

Ok, I'll post some urls:

http://www.sudoku.com/forums/viewtopic.php?t=143
http://www.sudoku.com/forums/viewtopic.php?t=183
http://www.sudoku.com/forums/viewtopic.php?t=199 (same technique but in a column)

http://www.sudoku.com/forums/viewtopic.php?t=142 (x-wing column)
http://www.sudoku.com/forums/viewtopic.php?t=124 (x-wing column)
http://www.sudoku.com/forums/viewtopic.php?t=105 (x-wing row)

You can also look at the Swordfish puzzles in 'Puzzles: plain text', which are even harder... (as in, it's a generalised X-wing, there are plenty of threads on this forum explaining it...)

itemone · Posted: Thu May 19, 2005 12:56 pm Post subject:

hi Psionman, I'd be interested in seeing your pseudo code. I'm using Lingo (Macromedia Director) for the coding, have successfully used this program in the past for sliding puzzles and encryptions/decryption routines etc..so I'm not looking for all the code to be served on a plate, the main enjoyment for me is creating the code from scratch.

I've completed a couple of puzzles in 'The Times Book', but now I quite fancy the challenge of writing a programme that'll solve the puzzles or even create them.

Any hints/tips would be greatly appreciated.

ItemOne

rallveird · Posted: Mon Jun 13, 2005 1:59 am Post subject:

If you want some puzzles to test on, check out:

http://www.menneske.no/sudoku/eng/

Should be pretty easy to find the hardest ones to test on.

markd · Posted: Mon Jul 04, 2005 2:48 pm Post subject:

Hi psionman,

I would be interested in seeing how you solved the puzzles using VB.

Hope you can help.

Regards,

Mark