The New Sudoku Players' Forum

[surendra.jain]

I have written a Kakuro Solver software that can solve Kakuro puzzles from logic. The source code to the Kakuro solver software can be freely downloaded from my website (sites.google.com/site/skjgeek). I have included some sample input files and also a README file on how to compile the code and prepare the input files. My Software is better than the few Kakuro solvers available in the internet.

I am attaching a Zip file of the Kakuro solver software with this post. Feel free to play around with it and send me your comments at : jainsk.iitkgp@gmail.com

[Mathimagics]

Hi Surendra,

I recall the discussion on your original question (Can all Kakuro be solved with pure logic)

I also posted this follow-up to that discussion (Kakuro and pure logic (revisited)).

Are you now saying that your program can solve ALL Kakuro puzzles without trial-and-error (ie without any form of DFS)?

Also, can you give us an overview of your approach - I will certainly try and test it, but actually reading other people's code to figure out how it ticks is not my favorite activity!

Cheers

[Mathimagics]

I will certainly try and test it, but actually reading other people's code to figure out how it ticks is not my favorite activity!

Especially when the code is written in Fortran! YECCH!

[Mathimagics]

I have built this with MinGW gfortran on Win32, but it crashes, no matter what input I use (mine or yours)

I introduced some write statements to trace its progress, and the fault appears to occur in routine BINDING_SQUARES

It looks like a problem with array indexing - someone is stepping on local memory!

BINDING_SQUARES has a rather ugly main loop (DO kcell = 1, bind_squares). The first few calls to this routine are well-behaved but then somewhere in that maze of "sudoku logic" code, the loop control variable kcell suddenly changes and so the loop control fails, and all hell breaks loose.

It either goes into an infinite loop, or crashes, which seems to indicate serious memory destruction (Code? Data?) is taking place.

I ran it with compiler option to check array bounds and hey presto, your SUM_ARRAY which has dimension 20, is quickly overflowing (as this log indicates):

Hidden Text: Show

Update pass = 0 , solved cells = 0
stage 1 solved_cells_final = 2
stage 2 solved_cells_final = 2
stage 3 solved_cells = 2
stage 4 solved_cells_Final = 2
-> Binding_squares
-> Binding_squares cage # 1
-> bind_squares = 2
sum_array( 1 ) = 7
sum_array( 2 ) = 8
sum_array( 3 ) = 9

sum_array( 1 ) = 2
sum_array( 2 ) = 3
sum_array( 3 ) = 4
-> Binding_squares cage # 2
-> bind_squares = 2
sum_array( 1 ) = 5
sum_array( 2 ) = 7

sum_array( 1 ) = 1
sum_array( 2 ) = 2
sum_array( 3 ) = 3

-> Binding_squares cage # 3
-> bind_squares = 4
sum_array( 1 ) = 16
sum_array( 2 ) = 17
sum_array( 3 ) = 18
sum_array( 4 ) = 17
sum_array( 5 ) = 18
sum_array( 6 ) = 19
sum_array( 7 ) = 18
sum_array( 8 ) = 19
sum_array( 9 ) = 20
sum_array( 10 ) = 19
sum_array( 11 ) = 20
sum_array( 12 ) = 21
sum_array( 13 ) = 17
sum_array( 14 ) = 18
sum_array( 15 ) = 19
sum_array( 16 ) = 18
sum_array( 17 ) = 19
sum_array( 18 ) = 20
sum_array( 19 ) = 20
sum_array( 20 ) = 21
sum_array( 21 ) = 22
sum_array( 22 ) = 21
sum_array( 23 ) = 22
sum_array( 24 ) = 23
sum_array( 25 ) = 18
sum_array( 26 ) = 19
sum_array( 27 ) = 20
sum_array( 28 ) = 19
sum_array( 29 ) = 20
.... etc

Your comment in code that "should never exceed 12" might be true for the number of different values, but you don't check whether the sums being added to the list are already there. I had to bump the array to 1000 before I got through without error (cage #8 went up to 830 entries).

Since the main (in fact the only) purpose of this table is to get a min/max value for these sums, I made sum_table have 45 entries, and just flagged each sum being added, then Find_Min_Max just looks for the first and last non-zero entries.

Now I have successfully completed one pass of BINDING_SQUARES, I have a new error:

Code: Select all

At line 1058 of file moves-arithmetic.f90
Fortran runtime error: Index '11' of dimension 1 of array
 'non_overlap_cells_vertical' above upper bound of 10


And that's where I have to leave it, I'm afraid!

[Mathimagics]

Well, I decided to have one last crack at it, so I decided to see if it would solve a 2x2 (yes!), I then expanded my tests, uncovering further array-bounds errors as I went, and was finally able to solve your 7x7 test example.

What I had to do to get it all going (at least able to solve 7x7 example):

• Replace the SUM_ARRAY with the 45-entry flag version I described above (you'd be wise to do the same, you appear to be bubble-sorting that table which is chock-full of duplicates, for no gain whatsoever)

• NUMBERS array in Eliminate_Hidden_Impossible had be extended since it obviouly found more than 3 candidates at some stage. I made it (9), to be sure.

• non_overlap_cells_vertical (and horizontal) were (10,2), but I had to increase them so I just set them to (100,2). Subroutine "calculate_crisscross_arithmetic" and "crisscross_arithmetic

It seems to get the answers right without falling over, so I imagine I'm on the right track!

What I simply can't understand is how this code was ever working on your system, unless your OS magically (and transparently) expands arrays on demand (and without being asked???).

[Mathimagics]

Tried to solve a different 7x7, came up with more array errors:

• naked_list(3,4,2): again this 1st dimension needed to be extended

• check_Contradiction_Adrianne: this function is called from kakuro_solve, and apparently it can return check_adrianne = 1 but at the same time nAdrianneStates is zero, so all the array references following are illegal

I'll try making these tables zero-based ....

---------------------
Aaagh!

This appears to be unresolvable - it appears that nAdrianneStates is simply not meant to be 0 at this point, making all the arrays 0-based just defers the problem, we still wind up with an index error, only it's -1 now ....

I give up!

Here are the specs for the puzzle I was trying to solve:

Hidden Text: Show

20 ! number of runs

14 2
1 3
1 4

10 2
1 6
1 7

28 4
2 1
2 2
2 3
2 4

3 2
2 6
2 7

29 6
3 1
3 2
3 3
3 4
3 5
3 6

41 7
4 1
4 2
4 3
4 4
4 5
4 6
4 7

28 6
5 2
5 3
5 4
5 5
5 6
5 7

17 2
6 1
6 2

15 4
6 4
6 5
6 6
6 7

16 2
7 1
7 2

4 2
7 4
7 5

17 5
1 3
2 3
3 3
4 3
5 3

42 7
1 4
2 4
3 4
4 4
5 4
6 4
7 4

35 6
1 6
2 6
3 6
4 6
5 6
6 6

3 2
1 7
2 7

16 3
2 1
3 1
4 1

29 6
2 2
3 2
4 2
5 2
6 2
7 2

28 5
3 5
4 5
5 5
6 5
7 5

19 3
4 7
5 7
6 7

16 2
6 1
7 1

But I find that it also happens with your "initial-1859", sadly ...

[surendra.jain]

Hi Surendra,

I recall the discussion on your original question (Can all Kakuro be solved with pure logic)

I also posted this follow-up to that discussion (Kakuro and pure logic (revisited)).

Are you now saying that your program can solve ALL Kakuro puzzles without trial-and-error (ie without any form of DFS)?

Also, can you give us an overview of your approach - I will certainly try and test it, but actually reading other people's code to figure out how it ticks is not my favorite activity!

Cheers

There are some very hard Kakuro puzzles that has to be solved using trial and error. What my code does is use logic and if it cannot solve the puzzle, it guesses the value of one of the cells from the possible values for that cell. It then uses logic to solve the puzzle from that point. If the guess value is false, then the code tries another value for that cell and follows the logic route until the guess value is true for that cell.

[surendra.jain]

Tried to solve a different 7x7, came up with more array errors:

• naked_list(3,4,2): again this 1st dimension needed to be extended

• check_Contradiction_Adrianne: this function is called from kakuro_solve, and apparently it can return check_adrianne = 1 but at the same time nAdrianneStates is zero, so all the array references following are illegal

I'll try making these tables zero-based ....

---------------------
Aaagh!

This appears to be unresolvable - it appears that nAdrianneStates is simply not meant to be 0 at this point, making all the arrays 0-based just defers the problem, we still wind up with an index error, only it's -1 now ....

I give up!



Here are the specs for the puzzle I was trying to solve:

Hidden Text: Show

20 ! number of runs

14 2
1 3
1 4

10 2
1 6
1 7

28 4
2 1
2 2
2 3
2 4

3 2
2 6
2 7

29 6
3 1
3 2
3 3
3 4
3 5
3 6

41 7
4 1
4 2
4 3
4 4
4 5
4 6
4 7

28 6
5 2
5 3
5 4
5 5
5 6
5 7

17 2
6 1
6 2

15 4
6 4
6 5
6 6
6 7

16 2
7 1
7 2

4 2
7 4
7 5

17 5
1 3
2 3
3 3
4 3
5 3

42 7
1 4
2 4
3 4
4 4
5 4
6 4
7 4

35 6
1 6
2 6
3 6
4 6
5 6
6 6

3 2
1 7
2 7

16 3
2 1
3 1
4 1

29 6
2 2
3 2
4 2
5 2
6 2
7 2

28 5
3 5
4 5
5 5
6 5
7 5

19 3
4 7
5 7
6 7

16 2
6 1
7 1

But I find that it also happens with your "initial-1859", sadly ...

I have run my code with all the input files in Linux using ifort compiler and it works fine. There are some checks that I should have done, but I omitted them (sorry about that) as they were not necessary. I have exhaustively checked my code and it works fine. Please check the code with ifort compiler.

[Mathimagics]

Please check the code with ifort compiler.

I downloaded a 30-day free trial of ifort. Your program behaved exactly the same as it did with gfortran.

I have exhaustively checked my code and it works fine.

Have you tested it with "check:all" (or "check:bounds") compiler option?

[surendra.jain]

I got the following result on running my code with your input kakuro puzzle :


-1 -1 5 9 -1 8 2

9 5 6 8 -1 2 1

2 1 3 6 8 9 -1

5 4 2 7 9 6 8

-1 2 1 5 4 7 9

9 8 -1 4 6 3 2

7 9 -1 3 1 -1 -1

[m_b_metcalf]

Especially when the code is written in Fortran! YECCH!

A remark based on ignorance or prejudice? Have you examined modern Fortran?

[Mathimagics]

Oops, did I hit a nerve?

Look I've been programming non-stop for coming up to 50 years, languages? I've seen them all, I even got paid to write Fortran once. So we can rule out ignorance, I hope.

That leaves us with prejudices: well I've had a long time to develop them, I've worked hard on them, I've earned them!

(I got a reaction like this when I described C as a dog's dinner. Which it is.)


PS: I followed your link after posting this, being a reasonable sort of person, and I'm really sorry to make fun of your baby, but come on!

[Mathimagics]

Mike, I'm happy to report that I have found a positive feature of modern Fortran!

The array cross-section constructs are, I must admit, impressive.

DFS solvers need to push copies of whole arrays onto a stack. I push/pop a 2D array (for my Grid state) and a 3D array (for my Domain state), and this nifty feature allows me to do it thusly:

Code: Select all

         ! PUSH:    save current Kgrid(*, *)  and Domain(*, *, *)
         Gstack(:,:,  KSP) = Kgrid
         Dstack(:,:,:,KSP) = Domain
         KSP = KSP + 1

         ! POP:     ' restore state
         KSP = KSP - 1
         Kgrid  = Gstack(:,:,  KSP)
         Domain = Dstack(:,:,:,KSP)


I notice that ifort is better at this than gfortran on my Win32 platform, presumably because it recognises that the cross-sections are contiguous, ie. each translates to a single mem copy.

[m_b_metcalf]

Mike, I'm happy to report that I have found a positive feature of modern Fortran!

[snip]

I notice that ifort is better at this than gfortran on my Win32 platform, presumably because it recognises that the cross-sections are contiguous, ie. each translates to a single mem copy.

Glad you like it. In general, ifort outperforms most other compilers, but it costs $$$. It's my understanding that gfortran is no longer so well supported whereas g95 even has most Fortran 2008 features, in particular coaarays (see also resource information).

Regards,

Mike