On Saturday, 25 August 2012 at 00:51:23 UTC, Chris Cain wrote:
On Friday, 24 August 2012 at 23:14:02 UTC, maarten van damme
wrote:
http://en.wikipedia.org/wiki/File:Sudoku_puzzle_hard_for_brute_force.jpg
It occurs to me that one of the main reasons why this
particular puzzle would be hard for brute force is that the
first line is blank and more than half of the second line is
blank, and it seems like it is designed to have as many choices
as possible before a set square is encountered.
I bet it could be solved much quicker by a computer by doing it
in reverse.
Is most likely. What would you do, have multiple threads all
solving it until one came with the fastest solution and then fix
it back to how it should be? It would work...
As a test I've taken the puzzle and converted it, normally I
gave it up after some 30 seconds but flipped it was 2 seconds.
As the picture puzzle shows:
..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9
Flipped:
....4...9..2.1....5......73.9.........4...1.....5.7.....1.2.........3.85.........
Strange, flipping it various ways and connecting them comes up
with an interesting patterns.
I've got some ideas, maybe I'll write a solution to this
myself. :)
Adding another level of possibilities removal before going to
brute force can definitely do a lot.
On Saturday, 25 August 2012 at 01:00:04 UTC, Timon Gehr wrote:
FWIW both mine and Maarten's solution require a trivial amount
of time to solve it.
Same for my C version of the solver. But that's not really the
topic here :P