HoDoKu

Programs which generate, solve, and analyze Sudoku puzzles

How to avoie bruteforce?

Postby sarker306 » Wed Apr 29, 2009 6:47 am

I think its a good think to make HoDoKu more efficient by adding some more techniques so that HoDoKu doesn't have to use BRUTE FORCE.
It will make this program a powerful analyzer (comparing to SE that doesn't use advanced fish, coloring, AIC, ALS, etc); resulting in fewer dependence on chains.
sarker306
 
Posts: 16
Joined: 06 March 2009

Re: How to avoie bruteforce?

Postby hobiwan » Wed Apr 29, 2009 7:23 am

sarker306 wrote:I think its a good think to make HoDoKu more efficient by adding some more techniques so that HoDoKu doesn't have to use BRUTE FORCE.
It will make this program a powerful analyzer (comparing to SE that doesn't use advanced fish, coloring, AIC, ALS, etc); resulting in fewer dependence on chains.

Hi sarker306,

unfortunately this is not as easy as it sounds! There are only a handful of possibilities to do it and most of them require extremely complex chains. Unfortunately I dont have much time at the moment, but what I am trying to do is to enhance HoDoKu's analyzing capabilities by adding some sort heuristics to the solving process.

Expanding the solver to be able to solve harder puzzles without brute force is definitely a gole, but not for the near future.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby daj95376 » Wed Apr 29, 2009 11:38 pm

I understand that you have other priorities besides working on HoDoKu. When you get the time, would you please review the following.

When I get to this point in solving my puzzle, HoDoKu reports the following two steps in its solution.

Code: Select all
.--------------.-----------------.-------------------.
| 5  89   6    | 3    7     *19  | 4     *18    2    |
| 2  4    1    | 6    5      8   | 79     379   39   |
| 3  89   7    | 19   4      2   | 158   -158   6    |
:--------------+-----------------+-------------------:
| 8  1    35   | 7    6      4   | 59     2     359  |
| 7  35   2    | 8    9     *13  | 6     *135   4    |
| 9  6    4    | 2    13     5   | 178   -1378  138  |
:--------------+-----------------+-------------------:
| 1  7    3589 | 59   38     6   | 2      4     589  |
| 4  25   589  | 159  128    7   | 3      6     1589 |
| 6  235  3589 | 4    1238  -139 | 1589  -1589  7    |
'--------------'-----------------'-------------------'

X-Wing: 1 r15 c68 => r369c8,r9c6<>1

Code: Select all
.----------------.-----------------.------------------.
| 5   89    6    | 3    7       19 | 4     18    2    |
| 2   4     1    | 6    5       8  | 79    379   39   |
| 3   89    7    | 19   4       2  | 158   58    6    |
:----------------+-----------------+------------------:
| 8   1     35   | 7    6       4  | 59    2     359  |
| 7  *35    2    | 8    9      *13 | 6     1-35  4    |
| 9   6     4    | 2    13      5  | 178   378   138  |
:----------------+-----------------+------------------:
| 1   7     3589 | 59   38      6  | 2     4     589  |
| 4   25    589  | 159  128     7  | 3     6     1589 |
| 6  *235  -3589 | 4    12-38  *39 | 1589  589   7    |
'----------------'-----------------'------------------'

X-Wing: 3 c26 r59 => r5c8,r9c35<>3

At this point, I want to see if selecting the X-Wing for <3> ahead of the X-Wing for <1> will affect the solution. I select the step with the X-Wing for <1> and then ask for all possible steps. However, only the X-Wing for <1> is listed along with ...

Code: Select all
Jellyfish: 3 r2467 c3589 => r5c8,r9c35<>3

Even if I restrict the size of Basic/Franken fish to 2/2, it still fails to list the X-Wing on <3>.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby hobiwan » Fri May 01, 2009 6:58 pm

daj95376 wrote:I understand that you have other priorities besides working on HoDoKu. When you get the time, would you please review the following.

It's not really a matter of priorities, it's more about earning my salary:D

I cant reproduce the error. Could you please PM me the contents of the file hodoku.hcfg in your temp directory (I think this has to be a side effect of a specific combination of options)?

Thanks!
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby hobiwan » Sat May 02, 2009 5:08 pm

daj95376,

thanks for the data, I can reproduce it now. This is apparently the same bug StrmCkr posted (see above): The X-Wing is only found if you search for Basic/Franken/Mutant Fish.

I will have to look into that a bit more, thanks a lot for your patience.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby hobiwan » Thu May 07, 2009 10:44 am

I made a maintenance relase today: Version 1.2.4

It should take care of the various bugs ind the fish search that had been introduced by the extended configuration options in version 1.2.

Features added:
    - #2772853: Use Ctrl-Cursor to go to next unsolved cell
Bugs fixed:
    - #2762372: In coloring not all possible eliminations were found
    - #2765903: Incorrect Siamese handling in Kraken search
    - #2765909: When searching for Kraken Fish ALS were always used
    - #2788800: "Only one fish per elimination" didn't return the smallest fish
    - #2788799: Search for all fishes finds Basic Fish only when searching for Mutant
    - #2788798: Search for Franken/Mutant returns Basic Fish
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Nice fish examples

Postby tarek » Sat Jun 18, 2011 12:05 pm

This post IIRC has been lost with the old forum. I found this backup by chance.

These were found in a group of NoFish with the help of Hodoku. Hodoku has really embraced the Ultimate fish guide & made it possible to find these beauties.

Code: Select all
Fish with 5 fins:
2..5......19.4......7...9..9.....7...4.1...8...5.38..26..2..5......8..1......7..3
After an Xy wing & Finned swordfish
.----------------------.----------------------.--------------------------.
| 2     *368    @3468  |  5     1679    1369  |  134-68  *3467    14-678 |
| 358    1       9     | *3678  4      *236   | #2368    @23567  #567    |
| 3458  *3568    7     |  368   126     1236  |  9       #23456   1456   |
:----------------------+----------------------+--------------------------:
| 9      2368   *12368 |  46    256     2456  |  7       *3456    1456   |
| 37     4       23    |  1     25679   2569  |  36       8       569    |
| 17    *67      5     | *4679  3       8     |  14       49      2      |
:----------------------+----------------------+--------------------------:
| 6      3789    1348  |  2     19      1349  |  5        479     4789   |
| 3457   23579   234   | *3469  8      *34569 | *246      1      *4679   |
| 1458   2589    1248  |  469   1569    7     |  2468    *2469    3      |
'----------------------'----------------------'--------------------------'
Finned Mutant Whale: 6 r268c38b1 r14c246b9 fr2c7 fr2c9 fr3c8 efr1c3 efr2c8 => r1c79<>6
V(13) XF(03) NF(02) EE(02) CE(00) PE(15)

Fish with 18 eliminations including 4 cannibalistic
.........75.13....29.87.............41.7..82.87..5.93..........5..3..78.38.92.51.
After 3 finned swordfish
.--------------------.--------------------------.----------------------------.
| 16   346   134-68  |  2456   469      245-69  |  1234-6   45-679   1235789 |
| 7    5    *468     |  1      3       *2469    | *246     *469     *24-689  |
| 2    9    *1346    |  8      7       *456     | *1346    *456     *1345-6  |
:--------------------+--------------------------+----------------------------:
| 69   236   235-69  |  24-6   14-689   123489  |  146      4567     145-67  |
| 4    1    *3569    |  7     *69      *3-69    |  8        2       *56      |
| 8    7    *26      | *246    5       *124-6   |  9        3       *146     |
:--------------------+--------------------------+----------------------------:
| 169  246   124-679 |  456    1468     145-678 |  2346     469      234-69  |
| 5    246   124-69  |  3      146      14-6    |  7        8        24-69   |
| 3    8    *467     |  9      2       *467     |  5        1       *46      |
'--------------------'--------------------------'----------------------------'
Franken Squirmbag: 6 r23569 c369b35 => r1c3678,r23478c9,r4c345,r5678c6,r78c3<>6
V(17) XF(00) NF(00) EE(18) CE(04) PE(18)

A Finned Franken Swordfish with an EndoFin
9..3.......6.7.1...8...5.2..6.........1.6.9..7......3..5.1...8...3.287.......4..2
somewhere down the line
.--------------------.-------------------------.---------------------.
| 9      1247  2457  |  3        148     126   | 4568   4567   45678 |
| 2345   234   6     |  2489     7       29    | 1      459    34589 |
| 134    8     47    | *469     *149     5     | 346    2     *34679 |
:--------------------+-------------------------+---------------------:
| 23458  6     24589 |  245789   1458-9  12379 | 2458   1457   14578 |
| 23458  234   1     |  24578    6       237   | 9      457    4578  |
| 7      249   24589 |  24589    1458-9  129   | 24568  3      14568 |
:--------------------+-------------------------+---------------------:
| 26     5     27    |  1       @39      67    | 34     8     *349   |
| 146    149   3     | *569      2       8     | 7      1569   1569  |
| 168    179   789   | *5679    *359     4     | 356    1569   2     |
'--------------------'-------------------------'---------------------'
Finned Franken Swordfish: 9 r37b8 c459 efr7c5 => r46c5<>9
V(07) XF(00) NF(01) EE(02) CE(00) PE(07)

Difficult to bypass Finned Jellyfish one stepper
7.....9...1.3..7....5.7..82..9.4....14.7.5.....793......4.2..13.2.5..8..6....32..
.-------------------.----------------------.-----------------------.
| 7      368   2368 |  12468  1568   12468 |  9      3456    1456  |
| 2489   1     268  |  3      5689   24689 |  7      456     456   |
| 349   *369   5    | *146    7     *1469  | *1346   8       2     |
:-------------------+----------------------+-----------------------:
| 2358  *3568  9    | *1268   4     *1268  | *1356  #23567  #15678 |
| 1      4     2368 |  7      68     5     |  3-6    2369    689   |
| 258   *568   7    |  9      3     *1268  | *1456  #2456   #14568 |
:-------------------+----------------------+-----------------------:
| 589    5789  4    | *68     2     *6789  | *56     1       3     |
| 39     2     13   |  5      169    14679 |  8      4679    4679  |
| 6      5789  18   |  148    189    3     |  2      4579    4579  |
'-------------------'----------------------'-----------------------'
Finned Jellyfish: 6 r3467 c2467 fr4c8 fr4c9 fr6c8 fr6c9 => r5c7<>6 (ED=8.8/8.8/8.3)
V(14) XF(04) NF(00) EE(01) CE(00) PE(06)
STTE

16 vertices Finned Jellyfish
4...3.......8.91...2.....3...71..9......5......84.72...9.....8...36.27..6...1...2
.--------------------------.------------------.-----------------------.
|  4        1-5678   1569  | 257   3     156  | 568    25679   56789  |
| *357     *3567    #56    | 8     2467  9    | 1     *24567  *4567   |
|  1-5789   2        1569  | 57    467   1456 | 4568   3       456789 |
:--------------------------+------------------+-----------------------:
| *235     *3456     7     | 1     268   368  | 9     *456    *34568  |
|  1239     1346     12469 | 239   5     368  | 3468   1467    134678 |
| *1359    *1356     8     | 4     69    7    | 2     *156    *1356   |
:--------------------------+------------------+-----------------------:
|  1257     9        1245  | 357   47    345  | 3456   8       13456  |
| *158     *1458     3     | 6     489   2    | 7     *1459   *1459   |
|  6        4578     45    | 3579  1     3458 | 345    459     2      |
'--------------------------'------------------'-----------------------'
Finned Jellyfish: 5 r2468 c1289 fr2c3 => r1c2,r3c1<>5
V(16) XF(01) NF(00) EE(02) CE(00) PE(09)

13 vertices finned Franken Swordfish
4..9......68.3.2..2....5.3.....4.3.....3.9.82....1.9..7....4.1..84.9.7..1..76....
Somewhere down the line
.---------------------.------------------.-----------------------.
| 4    *1357   *1357  | 9     278  12678 |  1-568   57     1578  |
| 59    6       8     | 14    3    17    |  2       4579   14579 |
| 2     17      179   | 1468  78   5     |  1468    3      14789 |
:---------------------+------------------+-----------------------:
| 589  *1257   *12579 | 2568  4    2678  |  3       567    157   |
| 6    *1457   *157   | 3     57   9     |  145     8      2     |
| 358  *23457  *2357  | 2568  1    2678  |  9       4567   457   |
:---------------------+------------------+-----------------------:
| 7     39      6     | 258   258  4     | #58      1      39    |
| 35    8       4     | 15    9    13    |  7       2      6     |
| 1    *2359   *235   | 7     6    38    | *458    *459   *34589 |
'---------------------'------------------'-----------------------'
Finned Franken Swordfish: 5 c23b9 r19b4 fr7c7 => r1c7<>5
V(13) XF(01) NF(00) EE(01) CE(00) PE(05)

9 vertices 4 Exofins Finned Swordfish
7..1.....5..8......83.97....7...53....148.9..6......82....4.7...6...12..9..2...13
.-------------------.------------------.------------------------.
|  7     249   2469 | 1     2356  2346 | 4568   #234569  #45689 |
|  5     1249  2469 | 8     236   2346 | 146    #234679  #14679 |
| *124   8     3    | 56    9     7    | 1-456  *2456    *1456  |
:-------------------+------------------+------------------------:
| *248   7     2489 | 69    126   5    | 3      *46      *146   |
|  23    235   1    | 4     8     236  | 9       567      567   |
|  6     3459  459  | 379   137   39   | 145     8        2     |
:-------------------+------------------+------------------------:
|  1238  1235  258  | 3569  4     3689 | 7       569      5689  |
| *348   6     4578 | 3579  357   1    | 2      *459     *4589  |
|  9     45    4578 | 2     567   68   | 4568    1        3     |
'-------------------'------------------'------------------------'
Finned Swordfish: 4 c189 r348 fr1c8 fr1c9 fr2c8 fr2c9 => r3c7<>4
V(09) XF(04) NF(00) EE(01) CE(00) PE(03)


10 vertices 4 eliminations Finned Franken Swordfish
3..6.....8.....9...26.4..3......47.....75..82....385...37.9..1.6....12..1..5.....
.--------------------------.------------------.---------------------.
|  3     *14579   *1459    | 6    1278  *2579 | 148   2457   14578  |
|  8      1457     145     | 123  127    2357 | 9     24567  14567  |
|  579    2        6       | 189  4      579  | 18    3      1578   |
:--------------------------+------------------+---------------------:
|  259    1568-9   12358-9 | 129  126    4    | 7     69     1369   |
| #49    *1469    *1349    | 7    5     *69   | 1346  8      2      |
|  2479   1467-9   124-9   | 129  3      8    | 5     469    1469   |
:--------------------------+------------------+---------------------:
|  245    3        7       | 248  9      26   | 468   1      4568   |
|  6     *4589    *4589    | 348  78     1    | 2     4579   345789 |
|  1     *489     *2489    | 5    2678   2367 | 3468  4679   346789 |
'--------------------------'------------------'---------------------'
Finned Franken Swordfish: 9 r15b7 c236 fr5c1 => r4c23,r6c23<>9
V(10) XF(01) NF(00) EE(04) CE(00) PE(05)


Enjoy
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Re: Nice fish examples

Postby hobiwan » Wed Aug 17, 2011 2:22 pm

Hi tarek,

tarek wrote:This post IIRC has been lost with the old forum. I found this backup by chance.


do you by any chance have a backup of the posts describing your "fish statistics" request? I have lost them, and since I have rewritten all of the fish code I cant really test it anymore.

Thanks
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Re: Nice fish examples

Postby tarek » Wed Aug 17, 2011 5:08 pm

hobiwan wrote:Hi tarek,

tarek wrote:This post IIRC has been lost with the old forum. I found this backup by chance.


do you by any chance have a backup of the posts describing your "fish statistics" request? I have lost them, and since I have rewritten all of the fish code I cant really test it anymore.

Hi hobiwan & nice to hear from you again,

I don't have the statistics request backed up...

The abbreviations however are for:

V: Vertices (the number of vertices in the fish pattern)
XF: eXoFins
NF: eNdoFins
PE: Potential eliminations (not vertices & not fins) ... (candidates in more cover sectors than base sectors)
EE: Eventual eliminations (The actual eliminations that fish causes) (PEs that see ALL fins)
CE: Cannibalistic eliminations (EEs that are in base sectors)

The definitions are in the Ultimate fish guide if you want a review.

The examples that were reposted above have all the statistical results as well if you need to comapare & retest results.

Tarek
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Re: HoDoKu

Postby hobiwan » Wed Aug 24, 2011 8:52 pm

Thank you anyway.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

New version

Postby hobiwan » Fri Oct 21, 2011 10:32 am

It has been a while I but finally got version 2.1 out. It includes a rewrite of all internal data structures and solver classes, which makes the solver two to three times faster than the old one (approx. 1.5ms per puzzle for the 17 collection on a i5 2.67GHz under w7 64bit). The new version is available for download on Sourceforge (user manual has not been updated yet).

Since the data structures were changed, the file format of the hsol files changed as well. Old hsol files should load correctly in the new version (puzzle plus solution paths) but savepoints stored in the files are lost.

Some of the new features:

    Hint pane and toolbar can now be hidden to improve the display on small screens
    New extended print options including a booklet printer
    Puzzles are now created in advance using a background thread; new puzzles appear instantly in most cases
    A new simplified mouse mode (optional)
    A progress marker
    Portable version: If a configuration file named hodoku.hcfg exists in the same directory as the program file, it is loaded automatically

The only change to the solving techniques is that URs/HRs now allow missing candidates.

Have fun!
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Re: HoDoKu

Postby SudoQ » Fri Oct 21, 2011 3:18 pm

Hi!

Since I use your program often I downloaded your new version.
I appreciate that you now can generate new puzzles without delay.
I've found that the program can sometimes freeze or generate a solution that contains steps like this (and do not give a solution):
”Template Set: r1c123456789,r2c13456789,r3c123456789,r4c12345789,r5c123456789,r6c1234679,r7c123456789,r8c12345679,r9c123456789=1”

Is that a bug or a feature?

/SudoQ
SudoQ
 
Posts: 39
Joined: 09 September 2011

Re: HoDoKu

Postby hobiwan » Fri Oct 21, 2011 4:58 pm

Hi SudoQ,

unfortunately this is a bug. Please deactivate the techniques "Template Set" and "Template Delete" for the time being. I will try and correct it as soon as possible.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

New version (again)

Postby hobiwan » Sun Oct 23, 2011 8:53 pm

I have released version 2.1.1, which should take care of the Template problem (among others).
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Re: HoDoKu

Postby SudoQ » Thu Nov 03, 2011 6:06 pm

Hi hobiwan,

When you generate puzzles it seems to be a gap in difficulty between level 'hard' and 'unfair'.
Would it be possible to insert a level there?

/SudoQ
SudoQ
 
Posts: 39
Joined: 09 September 2011

PreviousNext

Return to Software