The New Sudoku Players' Forum

[surendra.jain]

Dear All,

I have written a sudoku software that can solve sudoku puzzles from pure logic. The source code for the software can be found at my website : http://sites.google.com/site/skjgeek .

My website also contains source code to many other challenging and interesting computer puzzles (like killer sudoku, samurai sudoku, calcudoku, kakuro etc). Please feel free to download the source codes and share it among your friends.

I will appreciate your feedback.

Best Regards,
Surendra

[denis_berthier]

I have written a sudoku software that can solve sudoku puzzles from pure logic. The source code for the software can be found at my website : http://sites.google.com/site/skjgeek .
I will appreciate your feedback.

Hi Surendra,
I've downloaded your code and tried it on my Mac (OS X 10.10.5). (I tried both ""sudoku_solver" and "sudoku_solver_logic").
Using your command line: gfortran sudoku-logic.f90 moves.f90 moves-1.f90 moves-2.f90 moves-3.f90 moves-4.f90 moves-5.f90 (or gfortran Sudoku_solver.f90), I could compile both programs without any error or warning (BTW, I didn't have to install gfortran; it seems to be installed with the standard developer tools: Xcode...).
They work on the test examples you provided.

I have a few remarks:
- instead of a fixed name ("initial") for the puzzle file, it would be much easier and less error-prone to define it as a parameter, as the output file

- within the data file, the format is suitable if one wants to solve only one puzzle, but not convenient for series of puzzles. The usual format in this case is one puzzle per line, each puzzle being written as a sequence of 81 digits, e.g. for "test-very-hard-3":
500008001020006070008920300290700500007405200005009013004092600070600080300800002
The 0 could also be replaced by a dot, making it easier to see the givens (but it's not a real problem if everything has to be an integer for you, it's easy to modify the puzzle file):
5....8..1.2...6.7...892.3..29.7..5....74.52....5..9.13..4.926...7.6...8.3..8....2
Usually, the solver takes and solves one line after the other until it meets EOF

- for "sudoku_solver_logic", the output could be largely improved: instead of writing the values reached after each step, it'd be more interesting to say which rule has been applied and which candidates have been eliminated (most steps are eliminations, not value assertions)

- for "sudoku_solver" also, the output could be improved: of course, the detailed solution trace is not interesting, but you could output the depth reached by DFS

- there are lots of solvers around; it'd be interesting to output running times (for series of puzzles), so that we can compare

- all the test puzzles you provide are relatively easy

[m_b_metcalf]

I have written a sudoku software that can solve sudoku puzzles from pure logic. The source code for the software can be found at my website : http://sites.google.com/site/skjgeek .

My website also contains source code to many other challenging and interesting computer puzzles (like killer sudoku, samurai sudoku, calcudoku, kakuro etc). Please feel free to download the source codes and share it among your friends.

I will appreciate your feedback.

Surendra,
Thank you for setting up your very comprehensive website. I spent a while looking at the samurai section, and have the following comments that I hope you'll find useful.

I compiled the samurai code using the Intel compiler with no optimization and full debugging, and got an error message during execution at line 763 (sudoku_5(i_puzzle5,j_puzzle5) = 0), where a subscript has the out-of-range value of 0.

Compiling with optimization and without run-time checks, however, 'works'.

The format of your input file I found very confusing. It has no file extension and I assumed it was a text file (extension .txt, as with Notebook in Windows), but couldn't match what I saw with the READ statements in the code. I then realised that it is a document-style file (.doc, as with Word). Please note that it is usual to use text files, and for samurai the file in this forum typically looks like this:



Code: Select all

301500600096000001570000000038000009050380000002700050000000100007001004020004700  Tl
000006080000004073009120406040010005580060700000300600000000004002603000100092000  Tr
000000000003002080001004030008900700000650028000300140000000570800070062000030094  Br
025040807800002050009000203000007008090080710000001020060203000910006070300000000  Bl
100457000004900002700200100500030040610008530000090000807004000050000003203500001  Ce



(although the order of the five lines varies).

The sample puzzle that you supply (above) is solved by your code, but is a very poor example as the centre puzzle can be solved independently of the other four puzzles, using only singles. It even has 10 individually redundant clues:



Code: Select all

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

singles found 1 solution
  1  2  6  4  5  7  3  9  8
  3  8  4  9  6  1  7  5  2
  7  9  5  2  8  3  1  6  4
  5  7  9  1  3  2  8  4  6
  6  1  2  7  4  8  5  3  9
  4  3  8  6  9  5  2  1  7
  8  6  7  3  1  4  9  2  5
  9  5  1  8  2  6  4  7  3
  2  4  3  5  7  9  6  8  1
  1 6  is redundant
  2 4  is redundant
  3 7  is redundant
  5 8  is redundant
  6 5  is redundant
  8 2  is redundant
  8 9  is redundant
  9 1  is redundant
  9 3  is redundant
  9 4  is redundant



It is usual in samurais that no puzzle can be solved without input from a neighbour. The more interesting ones require not only the sharing of solved cells, but also the sharing of candidate values. Like this one:



Code: Select all

000870000090000030000400000400100008000003720000000600700040000000902010000000000 tl   Made of a 17-clue
000930000050000060000800000800700009000006340000000100300080000000504070000000000 tr   
000970000030000050000200000200800009000005760000000400700020000000306080000000000 br
000130000020000060000800000800700001000006340000000900300080000000204070000000000 bl
000570000000000000000600000600300005000008740000000200000060000000104000000000008 m



Further, one often tries to ensure that all four overlap regions are empty (as a point of honour).

As for the Fortran code itself, I'm surprised that you take so little advantage of Fortran's compact array notation. You start off by setting arrays to zero inside loops, where simple, whole-array assignments like sudoku_initial_1 = 0 would suffice. Also, the READ statements like

Code: Select all

     READ(10, *) sudoku_1(i,1),sudoku_1(i,2),sudoku_1(i,3),sudoku_1(i,4),sudoku_1(i,5), &
         sudoku_1(i,6),sudoku_1(i,7),sudoku_1(i,8),sudoku_1(i,9);print*, i, sudoku_1(i, 1), sudoku_1(i, 9)



could be simplified by the use of an array section, as in

Code: Select all

     READ(10, *) sudoku_1(i,:)



Finally, my old bug-bear, you continue to quote a so-called 'hardest' puzzle although it is no such thing. Please see the Hardest puzzle thread in this Forum.

HTH.

Regards,

Mike Metcalf

[surendra.jain]

I have updated my sudoku software with some most advanced techniques. Now, my sudoku software can solve even the hardest and toughest sudoku puzzles from pure logic. The source code for the sudoku software can be downloaded from my website :

sites.google.com/site/skjgeek

[m_b_metcalf]

I have updated my sudoku software with some most advanced techniques. Now, my sudoku software can solve even the hardest and toughest sudoku puzzles from pure logic. The source code for the sudoku software can be downloaded from my website :

Since surenda never deigns to reply to comments posted here, I'll not invest much time in this. I just note that:

the 'zip' files that one can download are, in fact, .rar files;

after trying logic methods, the program appears to resort to Thread of Ariadne, which is not logic but brute force;

he continues to cite a so-called 'hardest' puzzle although it is no such thing.

Mike Metcalf

[surendra.jain]

Dear Michael,

My sudoku software tries all possible logic before resorting to Adrianne's thread. You can puzzles at sudokuwiki.org (under the banner weekly unsolvable sudoku puzzles). The software in sudokuwiki.org cannot solve those puzzles. These puzzles cannot be solved by any known sudoku techniques and you have to resort to guessing when no other method works. The way it is implemented in my software is :
(1) I try all possible techniques until the sudoku is not advancing
(2) Call Adrianne's thread once (make a bet on a number of one of the squares)
(3) Try all possible techniques again (if the sudoku is stuck again at some late point, make another bet using Adrianne's thread)
(4) Repeat step 2-3 until you get a solution or you get to a point where your previous bet is found to be wrong. Then backtrack to the previous Adrianne's square and make a bet for another number and repeat step 2-3.

I will remove the "hardest sudoku" line from my website. But there are many sudoku puzzles available which can be solved only by making a guess at some point. I am implementing Trebor's table (that uses assertions and implications) when all other techniques have failed. But, it is near impossible to do Trebor's table by hand. You have to resort to computer to solve sudoku using Trebor's table. I will update my website once I am finished with it.

Surendra

[JasonLion]

My sudoku software tries all possible logic before resorting to Adrianne's thread.

No doubt you meant to say "... tries all of the logical techniques I have programmed before ...". Saying "tries all possible logic" is a very strong claim, something you have almost certainly not done. It would be really quite surprising if you have already programmed all of the known logical techniques, or even a simple majority of them. Based on your other comments it seems much more likely that you have done most of the basic techniques along with a few of the intermediate techniques and none of the really difficult ones. For example, do you have M-Wings or AIC or Mutant Fish (to name but a few)?

there are many sudoku puzzles available which can be solved only by making a guess at some point

I am not at all sure this is true. Of course there are many extremely difficult puzzles that no one has solved by hand yet. Essentially all of the famously impossible puzzles from a few years ago have been solved by hand at this point. The people who solve those puzzles use rather involved techniques that can take a day or two or more to locate by hand. Based on previous history it seems plausible that they can be solved by hand without guessing given one of the top solvers focuses on them for a few days. That at least is my belief, it hasn't been proven one way or the other yet.

Trebor's tables is considered brute force.