The New Sudoku Players' Forum

[sdk_fan]

I think the questions i had, are answered sufficiently.

I hope your conclusion is that all puzzles are solvable by a non T&E procedure. By the way, which one came with 0 result? Please give me the string.

The bad thing is, that i dont have an idea how to find a good order. Allways to take the band/stack with the least possible assignments in the units is often a bad strategy. I have the suspicion, that no better heuristics can be found, which dont take long to evaluate. So to define the order is a kind of guessing.

I hope you will at least agree that this kind of guessing is not that kind of guessing Sudoku players/programmers are talking about. But I will not use "guessing", I will use "strategy". I think the existing of choices and different strategies is good thing for Sudoku to continue to be a interesting puzzle game. I would say, if the true optimal could be easily computed, Sudoku would really be a dull thing, at least for programmers.

Of course you could avoid any memory problems by doing this depth first. Take the first assignment for the first unit, then the first of the combination with the next assignment, etc, until you have nothing or a solution. And then ... backtrack. All you would need in memory is, to save how to get to the next solution per level. This can be easily done, when all these vector arrays are kept in memory for all levels (units to combine) - you can calculate them, as soon you have defined the unit order. Then you just need a pointer to where you are.
Then i cant see any performance advantage for the breath first method.

I object the thought of backtracking in any case, once you decide to use cogwheels as the backbone of your solution. I will describe a thought here that handle the memory problem more aggressively, even accelerating the solving time (at least for hard puzzle with potential memory explosion with current engaging order).

We should start with the problem:
1. 50% of cpu time is spent on non-intelligent operation(for hard puzzles): cloning or copying.
2. Many copies are simply pruned without utilisation -- what a waste of time (CPU) and space (MEMORY)! Why copy in the first place!

Now the reasoning / description of my new proposal, which should able to suppress the memory issue.

Which step in the algorithm actually help you narrow down the space? -- Prune, and prune only. When does that happen? When, and only when cogwheel circles are formed. Which step gives you the memory problem? Graft, and graft only.

The interesting thing I find is that Prune and Graft are two independent operation.. Therefore, In the function NodeEngage, you replace

Code: Select all

If NextEngages is [ ]:          //No moret engaging level, attach the subtree from s(g)
      For each arc a common to MetaN and N:
         MetaGraft(MetaN.sons[a], N.sons[a])

with

Code: Select all

If NextEngages is [ ]:          //No moret engaging level, return
      return

you then get a prune-only version of engage(), which probably is no-longer proper to be called a engage(), so let us call this version -- "Intermesh()". Intermesh() will be useful at a moment I will call harping moment, because in the most typical form, the engaged groups form a shape somewhat like a harp whose strings are yet to be mounted.

Typical example of Harping moment (x's are cells that are covered by normally engaged groups. Their levels are already in tree c.)

Code: Select all

x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x
x x x
x x x
x x x
x x x
x x x x x x x x x


Each of C4-C9 will be the string of the harp, but engaging each string onto tree c will result in
1. some pruning of tree c because the string introduces some cogwheel circles, but also
2. many subtrees being grafted on the tree c (dramatically increasing the memory), because a string also come with five non-intersecting cells (in row4-8). And these cells do not (significantly) contribute to new circle formation any soon.

Pruning at this moment is overwhelmed by grafting (in hard puzzles) because of the weakness of the base of the harp.

My proposal at this moment is:
1. intermeshing C4-C9 onto tree c rather than engaging them onto tree c. This will accumulate prunning of the tree c before any unnecessary grafting is done!
2. after intermeshing them, normally engage one of these strings. Say, it is C9 being engaged.

Code: Select all

x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x           x
x x x           x
x x x           x
x x x           x
x x x           x
x x x x x x x x x


3. What do we have now? Another harping moment. Now the strings are R4-R8. Then you basically repeat the procedure.
Say, at the end of this round of intermeshing, we choose to engage R8.
4. What happens now? We can re-intermeshing string C4-C8, because, engaged cells in R8 allow the string C4-C8 to form new cogwheel circles.

[eleven]

By the way, which one came with 0 result? Please give me the string.

The bug was easy to fix - there were more possible assignments than i expected there could be.
I also made it faster by avoiding the STL lists size() function. It makes about 12 puzzles per minute and core now. But i also saw, that it still fails for some puzzles with a 4,8 mio limit (7 in the first 2100 puzzles of the list).

I object the thought of backtracking in any case, once you decide to use cogwheels as the backbone of your solution.

This is your decision. I just cant see, what should be better, when building the tree breadth first instead of depth first. All you need from your expanding tree can be calculated in forward, so why hold it in the memory.

I will describe a thought here that handle the memory problem more aggressively, even accelerating the solving time (at least for hard puzzle with potential memory explosion with current engaging order).

If i understood you, then what you are proposing, i already did at the very beginning. I go through the boxes and each of the 6 lines crossing it, and remove all assignments, which are not possible in both for the 3 intersecting cells. This is repeated, until no more removals are possible, which normally happens after the second round in the hard puzzles, when some 100 assignments have been cleared. Having done that, you will not find any more removals in the boxes of your example.
Maybe it is worth to do the same for the combinations of 2 boxes and each of the 3 lines in each band/stack, but of course this would take more time.

[eleven]

[Edit2:] After improving bad code, there is only one puzzle left, which could not be solved with a limit of 4.8 mio possible solutions in each level:

Code: Select all

..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686........7..6..5..


[sdk_fan]

[Edit2:] After improving bad code, there is only one puzzle left, which could not be solved with a limit of 4.8 mio possible solutions in each level:

Code: Select all

..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686........7..6..5..


Neither can I address it in 2GB! Very annoying. I have a feeling that this puzzle is constructed similarly as the very last one on wikipedia entry of sudoku algorithm. My solver addressed that one once, but not now, because I changed the order to add a unit. (EDIT: it IS　the same puzzle!)

However, I guess that my previous suggesting may work. And at this moment I do not think you can do that kind of accumulated pruning at the very beginning. But I can be wrong.
I will implement my thought when I have time, which I do not have at all. I will be away for a while, (but may peek in.)

[eleven]

With a lot of memory swapping i got a solution to the puzzle above with a maximum of 11.000,240 puzzles in memory after 6 minutes. But this is not the only monster for this method. The others did not make it into champagne's hardest list (ER 8.9-10.2).
Here are 10 more you will like. I did not find a solution with a limit of 10 mio.

Code: Select all

.........4...8...3.9...1......9.5.......6...26...2.4..3.....2.68...7...4..5....1.
..34...8.......1.......2..6....6.........12....98...7...5.984....7..3.5..3.5.....
..........5.1.92..6.......4...3...4..8..21......6....75..8.....7....3.5..3..1.9..
1.3.5.7...5......37....2.6....9..4..3...2...6.....8...5...1...7.....48.........9.
1..4....9..6.8.....7...1.6.2........3...2......7..3.2...19.....7....5.1...58..4..
.2.4..7.......9..6.......14.....1.......6..9..3.5..4..3.28......8..45.72......8..
.2.4....9.5...92.......254.....1...36.........3...492..7...5.9...8.........8....7
.....6....5.1....36...2.....7.9..3.5.....4.9.......4.8.1.8......8.7...3.7....58.1
........94....923..8.1......4..7....6....492..........3.2..5...5......92.64...35.
..3..67...5.1.....6...2..1...4.71..55..2...7.......3....5.9....8....2.9....8..4.. 


[sdk_fan]

With a lot of memory swapping i got a solution to the puzzle above with a maximum of 11.000,240 puzzles in memory after 6 minutes. But this is not the only monster for this method. The others did not make it into champagne's hardest list (ER 8.9-10.2).
Here are 10 more you will like. I did not find a solution with a limit of 10 mio.

Code: Select all

.........4...8...3.9...1......9.5.......6...26...2.4..3.....2.68...7...4..5....1.
..34...8.......1.......2..6....6.........12....98...7...5.984....7..3.5..3.5.....
..........5.1.92..6.......4...3...4..8..21......6....75..8.....7....3.5..3..1.9..
1.3.5.7...5......37....2.6....9..4..3...2...6.....8...5...1...7.....48.........9.
1..4....9..6.8.....7...1.6.2........3...2......7..3.2...19.....7....5.1...58..4..
.2.4..7.......9..6.......14.....1.......6..9..3.5..4..3.28......8..45.72......8..
.2.4....9.5...92.......254.....1...36.........3...492..7...5.9...8.........8....7
.....6....5.1....36...2.....7.9..3.5.....4.9.......4.8.1.8......8.7...3.7....58.1
........94....923..8.1......4..7....6....492..........3.2..5...5......92.64...35.
..3..67...5.1.....6...2..1...4.71..55..2...7.......3....5.9....8....2.9....8..4.. 


You're right, it seems the method has its own Achilles ankle. I find in these puzzles, givens are near
evenly dispersed in the grid.
My solver are also choked by most of them. But 2 are solved (phew, very close to 2GB limit), for example:

Code: Select all

>>> solvestring('.2.4....9.5...92.......254.....1...36.........3...492..7...5.9.
..8.........8....7')
Attacking..
Starting with...
col:  1 2 3 4 5 6 7 8 9
-----------------------
r 1 | _ 2 _ 4 _ _ _ _ 9
r 2 | _ 5 _ _ _ 9 2 _ _
r 3 | _ _ _ _ _ 2 5 4 _
r 4 | _ _ _ _ 1 _ _ _ 3
r 5 | 6 _ _ _ _ _ _ _ _
r 6 | _ 3 _ _ _ 4 9 2 _
r 7 | _ 7 _ _ _ 5 _ 9 _
r 8 | _ _ 8 _ _ _ _ _ _
r 9 | _ _ _ 8 _ _ _ _ 7

End with...
col:  1 2 3 4 5 6 7 8 9
-----------------------
r 1 | _ 2 _ 4 5 _ _ _ 9
r 2 | _ 5 _ _ _ 9 2 _ _
r 3 | _ _ _ _ _ 2 5 4 _
r 4 | _ _ _ _ 1 _ _ _ 3
r 5 | 6 _ _ _ _ _ _ _ _
r 6 | _ 3 _ _ _ 4 9 2 _
r 7 | _ 7 _ _ _ 5 _ 9 _
r 8 | _ _ 8 _ _ _ _ _ _
r 9 | _ _ _ 8 _ _ _ _ 7

Not solved in the pre-processing. Now Using Cogwheel Method
col:     1       2       3       4       5       6       7       8       9
--------------------------------------------------------------------------
r 1   8137| D    2|   1367| D    4| D    5|  81367|  81367|  81367| D    9|
--------------------------------------------------------------------------
r 2  81347| D    5|  13467|   1367|   8367| D    9| D    2|  81367|    816|
--------------------------------------------------------------------------
r 3  81397|   8169|  13967|   1367|   8367| D    2| D    5| D    4|    816|
--------------------------------------------------------------------------
r 4 245789|    894|  92457|  92567| D    1|    867|   8467|   8567| D    3|
--------------------------------------------------------------------------
r 5 D    6|   8149| 124579|  92357|  89237|    837|   8147|   8157|   8145|
--------------------------------------------------------------------------
r 6   8157| D    3|    157|    567|    867| D    4| D    9| D    2|   8156|
--------------------------------------------------------------------------
r 7   1234| D    7|  12346|   1236|   2346| D    5|  81346| D    9|  81246|
--------------------------------------------------------------------------
r 8 123459|   1469| D    8| 123679| 234679|   1367|   1346|   1356|  12456|
--------------------------------------------------------------------------
r 9 123459|   1469| 1234569| D    8|  92346|    136|   1346|   1356| D    7|
--------------------------------------------------------------------------
Tree built for group [(3, 9), (2, 9), (5, 9), (8, 9), (6, 9), (7, 9)]
Tree built for group [(3, 9), (2, 9), (1, 8), (1, 7), (2, 8)]
0:00:18.692 spent, 36 leaves (paths), 2 groups engaged.
Tree built for group [(5, 9), (6, 9), (4, 7), (4, 8), (5, 7), (5, 8)]
0:00:00.025 spent, 216 leaves (paths), 3 groups engaged.
Tree built for group [(1, 8), (2, 8), (4, 8), (5, 8), (8, 8), (9, 8)]
0:00:00.032 spent, 360 leaves (paths), 4 groups engaged.
Tree built for group [(8, 9), (7, 9), (8, 8), (9, 8), (8, 7), (9, 7), (7, 7)]
0:00:00.041 spent, 688 leaves (paths), 5 groups engaged.
Tree built for group [(6, 9), (6, 5), (6, 3), (6, 4), (6, 1)]
0:00:00.093 spent, 1568 leaves (paths), 6 groups engaged.
Tree built for group [(6, 5), (6, 4), (5, 6), (4, 6), (5, 4), (4, 4), (5, 5)]
0:00:00.679 spent, 7168 leaves (paths), 7 groups engaged.
Tree built for group [(5, 9), (5, 7), (5, 8), (5, 6), (5, 4), (5, 5), (5, 2), (5
, 3)]
0:00:00.825 spent, 24608 leaves (paths), 8 groups engaged.
Tree built for group [(4, 7), (4, 8), (4, 6), (4, 4), (4, 2), (4, 3), (4, 1)]
0:00:01.240 spent, 19168 leaves (paths), 9 groups engaged.
Tree built for group [(5, 6), (4, 6), (9, 6), (8, 6), (1, 6)]
0:00:03.070 spent, 53376 leaves (paths), 10 groups engaged.
Tree built for group [(1, 8), (1, 7), (1, 6), (1, 3), (1, 1)]
0:00:03.312 spent, 111520 leaves (paths), 11 groups engaged.
Tree built for group [(9, 8), (9, 7), (9, 6), (9, 2), (9, 5), (9, 1), (9, 3)]
0:00:13.750 spent, 70096 leaves (paths), 12 groups engaged.
Tree built for group [(5, 2), (4, 2), (9, 2), (3, 2), (8, 2)]
0:00:12.051 spent, 381848 leaves (paths), 13 groups engaged.
Tree built for group [(8, 9), (8, 8), (8, 7), (8, 6), (8, 2), (8, 1), (8, 5), (8
, 4)]
0:00:16.881 spent, 148880 leaves (paths), 14 groups engaged.
Tree built for group [(6, 5), (5, 5), (9, 5), (8, 5), (7, 5), (2, 5), (3, 5)]
0:00:12.641 spent, 133296 leaves (paths), 15 groups engaged.
Tree built for group [(1, 6), (2, 5), (3, 5), (3, 4), (2, 4)]
0:00:13.829 spent, 283360 leaves (paths), 16 groups engaged.
Tree built for group [(6, 4), (5, 4), (4, 4), (8, 4), (3, 4), (2, 4), (7, 4)]
0:00:10.762 spent, 312064 leaves (paths), 17 groups engaged.
Tree built for group [(3, 9), (3, 2), (3, 5), (3, 4), (3, 1), (3, 3)]
0:00:02.785 spent, 77280 leaves (paths), 18 groups engaged.
Tree built for group [(7, 9), (7, 7), (7, 5), (7, 4), (7, 1), (7, 3)]
0:00:12.083 spent, 95272 leaves (paths), 19 groups engaged.
Tree built for group [(6, 3), (5, 3), (4, 3), (1, 3), (9, 3), (3, 3), (7, 3), (2
, 3)]
0:00:01.239 spent, 4181 leaves (paths), 20 groups engaged.
Tree built for group [(2, 9), (2, 8), (2, 5), (2, 4), (2, 3), (2, 1)]
0:00:00.239 spent, 1 leaves (paths), 21 groups engaged.
Tree built for group [(9, 6), (8, 6), (9, 5), (8, 5), (8, 4), (7, 5), (7, 4)]
0:00:00.034 spent, 1 leaves (paths), 22 groups engaged.
Tree built for group [(1, 3), (1, 1), (3, 2), (3, 1), (3, 3), (2, 3), (2, 1)]
0:00:00.034 spent, 1 leaves (paths), 23 groups engaged.
Tree built for group [(1, 7), (4, 7), (5, 7), (8, 7), (9, 7), (7, 7)]
0:00:00.018 spent, 1 leaves (paths), 24 groups engaged.
Tree built for group [(6, 3), (6, 1), (5, 2), (5, 3), (4, 2), (4, 3), (4, 1)]
0:00:00.032 spent, 1 leaves (paths), 25 groups engaged.
Tree built for group [(9, 2), (9, 1), (9, 3), (8, 2), (8, 1), (7, 1), (7, 3)]
0:00:00.070 spent, 1 leaves (paths), 26 groups engaged.
Tree built for group [(6, 1), (4, 1), (1, 1), (9, 1), (8, 1), (3, 1), (7, 1), (2
, 1)]
0:00:00.184 spent, 1 leaves (paths), 27 groups engaged.
The puzzle has been decided. Time spent in the cogwheel method: 0:01:45.968000
There are 1 solutions.
Solution #1:
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 2 3 1
7 8 9 1 3 2 5 4 6
2 4 5 9 1 8 6 7 3
6 9 7 5 2 3 8 1 4
8 3 1 6 7 4 9 2 5
3 7 4 2 6 5 1 9 8
5 1 8 3 9 7 4 6 2
9 6 2 8 4 1 3 5 7
Garbage: 3640228
>>>

Hopefully, I can address this issue after my exam.

[eleven]

This again shows, how strongly the performance depends on the selected order.

When i used your order, my program solved it within a second.
I also tried the order i get, when i take the bands/stacks and within them the groups in the order of least assignments (with the restriction, that there always must be overlapping cells). This one took 8 seconds, i.e. about 10 times slower, and needed 5 times more memory. So i was wrong, that its always a good strategy to make full bands/stacks.
I guess that to any heuristic to find a good order you also can find a puzzle, for which it is a bad one.

Good luck for your exam.

[sdk_fan]

This again shows, how strongly the performance depends on the selected order.

When i used your order, my program solved it within a second.
I also tried the order i get, when i take the bands/stacks and within them the groups in the order of least assignments (with the restriction, that there always must be overlapping cells). This one took 8 seconds, i.e. about 10 times slower, and needed 5 times more memory. So i was wrong, that its always a good strategy to make full bands/stacks.
I guess that to any heuristic to find a good order you also can find a puzzle, for which it is a bad one.

Good luck for your exam.

Thank you. This must be my last post for the next 4 weeks.....

For the wikipedia one, my heuristics says using this order (but still exceeding 2GB for the solver proper):

Code: Select all

set([(8, 9), (5, 9), (3, 9), (9, 9), (1, 9)])
set([(2, 7), (3, 8), (1, 8), (3, 9), (1, 9), (1, 7)])
set([(2, 7), (4, 7), (6, 7), (5, 7), (7, 7), (8, 7), (1, 7)])
set([(5, 9), (4, 7), (6, 7), (6, 8), (5, 7), (5, 8)])
set([(9, 8), (7, 7), (9, 9), (8, 9), (8, 8), (8, 7)])
set([(4, 7), (4, 4), (4, 1), (4, 6), (4, 3)])
set([(6, 4), (4, 6), (5, 6), (4, 4), (6, 5), (5, 5)])
set([(6, 4), (6, 7), (6, 8), (6, 1), (6, 3), (6, 2), (6, 5)])
set([(5, 9), (5, 5), (5, 6), (5, 7), (5, 1), (5, 2), (5, 8), (5, 3)])
set([(8, 3), (9, 3), (6, 3), (2, 3), (4, 3), (5, 3)])
set([(9, 2), (9, 8), (9, 3), (9, 9), (9, 5), (9, 6)])
set([(5, 5), (1, 5), (9, 5), (8, 5), (6, 5), (3, 5)])
set([(8, 3), (8, 2), (8, 9), (8, 8), (8, 7), (8, 6), (8, 5), (8, 4)])
set([(2, 7), (2, 6), (2, 3), (2, 4), (2, 2)])
set([(2, 6), (4, 6), (5, 6), (7, 6), (1, 6), (3, 6), (8, 6), (9, 6)])
set([(3, 2), (3, 1), (3, 8), (3, 9), (3, 6), (3, 4), (3, 5)])
set([(6, 4), (4, 4), (1, 4), (7, 4), (3, 4), (2, 4), (8, 4)])
set([(7, 4), (7, 6), (7, 7), (7, 2), (7, 1)])
set([(7, 1), (6, 1), (3, 1), (5, 1), (4, 1), (1, 1)])
set([(1, 2), (1, 4), (1, 5), (1, 8), (1, 6), (1, 9), (1, 7), (1, 1)])
set([(2, 6), (1, 4), (1, 5), (1, 6), (3, 6), (3, 4), (2, 4), (3, 5)])
set([(8, 5), (7, 6), (7, 4), (8, 6), (9, 5), (9, 6), (8, 4)])
set([(6, 8), (9, 8), (3, 8), (1, 8), (8, 8), (5, 8)])
set([(4, 1), (6, 1), (6, 3), (6, 2), (4, 3), (5, 1), (5, 2), (5, 3)])
set([(8, 3), (8, 2), (7, 1), (9, 2), (9, 3), (7, 2)])
set([(1, 2), (3, 2), (3, 1), (2, 3), (2, 2), (1, 1)])
set([(1, 2), (3, 2), (8, 2), (9, 2), (6, 2), (2, 2), (5, 2), (7, 2)])

Just wonder if it works as well for your program. I guess if I implement my python script in C++, I will have a big acceleration too. Should I pick c++ which I have not used for 15 years? Perhaps no. But I envy you can program it in c++ so fast.

By the way, I was initially taking your strategy: find units with most overlapping cells. But later I realised that overlapping without circle formation only decrease the speed of memory explosion, never able to decrease it; only circle-forming unit can potentially decrease memory usage, but this also depend on how big is the space introduced by non-overlapping cells. That is why my heuristic always picks a row and a col after forming a stack and a band, which is obviously not good enough.

Anyway, I think, although any reasonable heuristics may not work perfectly on every puzzle, overall we should be able to see if the performance of the method correlates better with search-based methods or with logic-based methods.

[eleven]

Just wonder if it works as well for your program.

Yes, this order works very fine with less than 3 mio solutions/level, solved in 3 seconds.

The hardest level was with adding row 2:
c9,b3,c7,b6,b9,r4,b5,r6,r5, c3,r9,c5,r8,r2,
c6,r3,c4,r7, c1,r1,b2,b7,c8,b4,b7,b1,c2

Code: Select all

       10   12 15  3   1
   . . x | . x . | x x x
14 o o x | o o o | x 2 x
   . . x | . x . | x x x
  -------+-------+-------
 6 x x x | x x x | x x x
 9 x x x | x 7 x | x 4 x
 8 x x x | x x x | x x x
  -------+-------+-------
   . . x | . x . | x x x
13 x x x | x x x | x 5 x
11 x x x | x x x | x x x

When doing c6 before r2 its even better - 2 secs, max 1.8 mio.

[Added:]
PS: This order also needs 2 sec, with a little lower max. of 1.77 mio:
c9,b6,b3,b9,c7,r4,b5,r6,r5,c3,c1,r2,b1,r7,b7,r9,r3,c5,r1,c4,b8,c8,c6,b2,b4,r8,c2

Code: Select all

  11   10          5   1
   x x x | . . . | x x x
12 x13 x | x x x | x 3 x
   x x x | . . . | x x x
  -------+-------+-------
 6 x x x | x x x | x x x
 9 x x x | x 7 x | x 2 x
 8 x x x | x x x | x x x
  -------+-------+-------
14 x o x | o o o | x x x
   x15 x | . . . | x 4 x
   x . x | . . . | x x x

r1: 8 cells, 534 assignments 
r2: 5 cells,  50 assignments
r3: 7 cells, 146 assignments
r4: 5 cells,  24 assignments
r5: 8 cells, 282 assignments
r6: 7 cells,  96 assignments
r7: 5 cells,  50 assignments
r8: 8 cells, 889 assignments
r9: 6 cells,  62 assignments
c1: 6 cells,  92 assignments
c2: 8 cells, 689 assignments
c3: 6 cells,  58 assignments
c4: 7 cells, 241 assignments
c5: 6 cells, 142 assignments
c6: 8 cells, 537 assignments
c7: 7 cells,  64 assignments
c8: 6 cells,  70 assignments
c9: 5 cells,  38 assignments
b1: 6 cells,  96 assignments
b2: 8 cells, 588 assignments
b3: 6 cells,  46 assignments
b4: 8 cells, 338 assignments
b5: 6 cells,  44 assignments
b6: 6 cells,  38 assignments
b7: 6 cells,  96 assignments
b8: 7 cells, 462 assignments
b9: 6 cells,  54 assignments


[sdk_fan]

Finally, I have implemented the idea I described about memory suppression. Basically, I modified the heuristics of circle finding. Still some adjustments need to be done, but those puzzles with memory issues are solvable now. The wikipedia one which crashed my solver is now solved in 96 sec, memory peaked at 900MB. The one which was solved without this technique (@ 106 sec, 1.2 GB) is now solved in 28 sec, 280MB. I cannot say the memory problem won't happen, but the such situation should be rarer now.

[eleven]

Welcome back, hope all went right with the exam.

Fine, that you managed to avoid memory problems for those puzzles.
To be honest, i am already far away off this topic, i did nothing more with it.

[sdk_fan]

Welcome back, hope all went right with the exam.

Fine, that you managed to avoid memory problems for those puzzles.
To be honest, i am already far away off this topic, i did nothing more with it.

Thanks. It seems to me there is nothing more to talk about the topic, except that I find out the algorithm (i.e., engage()) is actually equivalent to the "natural join" of two tables, which is a standard database operation. There are many database approaches to the Sudoku problem but I cannot google "natural join" and Sudoku.

The only thing bothering me is whether the method will be truly useful in dealing with massive Sudoku boards, which come with a huge search space.

Today I was solving a jigsaw Sudoku which Andrew Stuart sent me (as a challenge to my method, i guess. He said he can never wait his solver to complete searching, which may take days).

Code: Select all

Blocks='\
777776666\
711277786\
112233386\
122335586\
123345886\
123445896\
123455899\
124459889\
444559999'

puzzle='\
_____6___\
______7__\
_______8_\
1________\
_2_______\
__3______\
___4_____\
____5____\
_________'

My solver was not able to solve it directly due to the memory explosion. But after 10902 trials (out of 12502) and 30 min, it is solved.

[sdk_fan]

I spent too much time on Sudoku solver programming in the past 5 months. I think it will be good for me to pause for a while. It will be appropriate for me to report here the current status of the algorithm, which is still in Python.

First, I want to re-emphasize the equivalence of the algorithm to "natural join" of 27 tables, which is a standard database operation. (There are already existing database approach to Sudoku, however, to my best knowledge, none in the form of natural join.) It is well known that the performance (time and space) of joining a list of tables is heavily dependent on the order of joining, and I was simply repeating it. I do not want to continue the debate about if the algorithm is in nature T&E or what. As I mentioned, it is a matter of interpretation; and T&E is the mother of all logic (and a lot more), not a taboo thing at all.

Secondly, although there is an equivalence, I think using database per-se to solve Sudoku may not be the optimal approach, since you lose the control to the data structure of the "table", which could be handled by more flexible data structure in other programming languages.

Particularly, I report here that I further reduced the computing time/space by improving the data structure and storing non-intersecting cells in a more compact form -- group (or subset in Sudoku terminology)

The basic structure is still a tree, but a leaf node is now a container of a list of "groups" (as defined in my paper). When a new unit is being presented as a tree, not all its cells will be expanded as a layer of the tree; only those cells that intersect with the covered cells in the main tree (non-leaf and leaf layer) will be expanded as a non-leaf layer; each path is an assignment of these intersecting cells, which leads to the leaf, which contains a proper group information for the non-intersecting cells. In a leaf there is a list of groups instead of one group -- one reason is that if a group can contain subgroups, in this case, the group is actually the cross product, or "Descartes product", of subgroups.

The joining procedure (engage()), now has a new sub-algorithm extracting a cell in the leaf layer of the main tree and form a new non-leaf layer, to couple with a corresponding non-leaf layer of the unit-tree; but at the end of the sub-algorithm, I end up with doing a "descartes product" of two leaf nodes -- one from the main tree, one from the unit-tree; the "descartes product" is a symbolic operation -- you simply copy-merge the two sets of groups from the two leaves, (However, I still use the concept of metaleaf in the actual algorithm)

Therefore, in the middle of the computation, only intersecting cells are expressed as non-leaf layers, while those covered but non-intersecting cells stay in the leaves as a part of some groups.

I implemented this modification, but without the "intermeshing" idea I described earlier and implemented in another version. I think this modification on data structure is more basic. But still, I can save 60-70% of memory, and speed up computation 2-10 times faster than the intermeshing version. So I suppose, including the intermeshing technique would still improve the performance for hard puzzles.

I can even further save the memory -- about another 40%, because many leaves contains identical group, and therefore one group can be shared between leaves. In theory, the memory save is significant (95% for hard puzzles, if not more) when groups are shared. I like the idea very much, and I implemented it, spending much time in debugging -- and it works. However, the overhead is considerable -- a new data structure is needed to remember which leaves contain a same group. The overall result is mere 40% of memory save and an almost doubled computation time (of the non-sharing version). Profiling shows much of computation (50%) is spent maintaining the new data structure -- it is the "union" operation of two sets of leaves (while in the non-sharing version, the most time consuming is copy, in fact, "union" of groups).

Although this version does not improve speed, I feel satisfied to see the nice relation between leaves and groups -- actually the relation between partial assignments and groups. This relation meets very well my early intuition that "cores" -- ie,"groups with no subgroups" can be interesting object to consider.

Is there room to still improve the performance of the algorithm? Perhaps yes, for example, in my fastest version, the function "find_subgroups" takes 20% of CPU time (just next to copy-merge leaves). My way to do it is to check each combination of cells, so the worst scenario is 2^n checks for a group of size n. I guess there exist more efficient algorithms.

However, I feel satisfied to see "find_subgroups" -- or "finding subsets" -- is on the top of the profiling result, because I believe finding subsets is one of the core operations of Sudoku game.

[eleven]

Hi, thanks for the summary.

First, I want to re-emphasize the equivalence of the algorithm to "natural join" of 27 tables, which is a standard database operation. (There are already existing database approach to Sudoku, however, to my best knowledge, none in the form of natural join.)

Can you tell me, whats the difference to lerxst's aproach ?

Did you also give it a thought, that you could do it depth first as well ? As far as i remember, my implementation would not have been much slower without any memory problems then.

[lerxst]

Particularly, I report here that I further reduced the computing time/space by improving the data structure and storing non-intersecting cells in a more compact form -- group (or subset in Sudoku terminology)

The basic structure is still a tree, but a leaf node is now a container of a list of "groups" (as defined in my paper). When a new unit is being presented as a tree, not all its cells will be expanded as a layer of the tree; only those cells that intersect with the covered cells in the main tree (non-leaf and leaf layer) will be expanded as a non-leaf layer; each path is an assignment of these intersecting cells, which leads to the leaf, which contains a proper group information for the non-intersecting cells. In a leaf there is a list of groups instead of one group -- one reason is that if a group can contain subgroups, in this case, the group is actually the cross product, or "Descartes product", of subgroups.

The joining procedure (engage()), now has a new sub-algorithm extracting a cell in the leaf layer of the main tree and form a new non-leaf layer, to couple with a corresponding non-leaf layer of the unit-tree; but at the end of the sub-algorithm, I end up with doing a "descartes product" of two leaf nodes -- one from the main tree, one from the unit-tree; the "descartes product" is a symbolic operation -- you simply copy-merge the two sets of groups from the two leaves, (However, I still use the concept of metaleaf in the actual algorithm)

Just to clarify, by "Descartes product", do you mean "Cartesian product" ("produit cartésien" in French ) ?