SoylentNews

Solving Logic Puzzles in Fortran

posted by LaminatorX on Wednesday July 02 2014, @12:34PM   
from the Which-Door-would-He-Suggest? dept.

gambit writes:

Computational nanoscientist Surendra Jain has written solvers for Sudoku, Killer Sudoku, Samurai Sudoku, Calcudoku, Kakuro and many other logic problems.

All are elegantly coded and very fast: for example, the "World's Hardest Sudoku" is solved in 0.05 seconds (on a 5 year old PC) and his Knight's Tour solver is an order of magnitude faster than this one.

The page (called "Classical Geek") has all source (in Fortran 90, one of the most popular languages in high-performance computing) as well as compilation and running instructions.

• Re:Logic vs Brute force?(Score: 2) by gringer on Thursday July 03 2014, @01:53AM

  by gringer (962) on Thursday July 03 2014, @01:53AM (#63369)

  If i'm not misstaken it looks at cells with few options and try all the possible combos and see if one fits? I could be wrong. But arn't these puzzels supposed to be be solved by logical steps and not by trying every possible combination until one fits; which is the brute force method.

  Yes, that appears to be the case. This also means that using this solver to generate puzzles will end up in pain and misery.

  I am of the opinion that a proper sudoku solver should be able to give an "I don't know" answer (or perhaps, "that looks ambiguous") in response to the question, "can this be solved?" My J2Me sudoku puzzle generator / solver does this, and will correspondingly only generate puzzles that are unambiguous (although they might be a bit too easy for experienced sudoku players):

  http://users.actrix.co.nz/jessicac/JMeSudoYu.jad [actrix.co.nz]

  However, the one here does not deal approriately with ambiguous puzzles. The following puzzle is ambiguous, because both 1 and 2 can satisfy a correct solution when placed in the top left hole:
  
  0 0 3 4 5 6 7 8 9
  7 8 9 1 2 3 4 5 6
  4 5 6 7 8 9 1 2 3

  0 0 4 3 6 7 8 9 5
  8 6 7 9 1 5 3 4 2
  3 9 5 8 4 2 6 7 1

  5 7 1 6 9 4 2 3 8
  6 4 2 5 3 8 9 1 7
  9 3 8 2 7 1 5 6 4
  

  The fortran code provided here will give a solution for this puzzle, when the correct answer should be "ambiguous". Because the problem space of sudoku is not fully known (i.e. there are some hard puzzles that have only one solution, but brute force is necessary to find it), a brute force algorithm is necessary if you want to verify that a puzzle is truly ambiguous, but giving an "I don't know" answer is very possible without brute forcing things.

  --
  Ask me about Sequencing DNA in front of Linus Torvalds [youtube.com]

  Parent

  Starting Score:	1		point
  Karma-Bonus Modifier		+1
  Total Score:		2