Solving Japanese crosswords with SAT Solver

 3r3407. 3r3-31. On Habré there were several articles on solving Japanese crosswords, where the authors came up with various ways to solve such crosswords. In the commentary on article Solving color Japanese crosswords with the speed of light I suggested that, since the solution of Japanese crosswords is an NP-complete task, then they must be solved using an appropriate tool, namely, the SAT solver. Since my idea was met with quite skepticism, I decided to try to implement it and compare the results with other approaches. What came out of this can be found under the cut. 3r33394.  3r3407. Survey of Paint-by-Number Puzzle Solvers . This site has a table comparing the speed of various applications for solving Japanese crossword puzzles and a good set of examples - from the easiest ones that are solved by everyone, to complex ones that only one application solves. These results were obtained on a computer with a 2.6GHz AMD Phenom II X??? quad-core 64-bit processor Memory: 8 Gb. I used an Intel® Core (TM) i7-2600K CPU @ ???GHz Memory 16 Gb computer. 3r33394.  3r3407. 3r33394.  3r3407. As a result, I obtained the following results:
 3r3407. 3r33394.  3r3407.
======== sample-nin /webpbn-00001.nin ========
Start read data. 3r3407. 16 lines were read
Solver started. vars = 150
Clauses = 562
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?610s
user 0m???s
sys 0m???s
========= sample-nin /webpbn-00006.nin ========
Start read data. 3r3407. 41 lines were read
Solver started. vars = 1168
Clauses = 10215
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?053s
user 0m?028s
sys 0m?000s
========= sample-nin /webpbn-00016.nin ========
Start read data. 3r3407. 69 lines were read
Solver started. vars = 7484
Clauses = 191564
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?368s
user 0m???s
sys 0m???s
========= sample-nin /webpbn-00021.nin ========
Start read data. 3r3407. 40 lines were read 3r3407. Solver started. vars = 1240
Clauses = 11481
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?095s
user 0m???s
sys 0m?000s
========= sample-nin /webpbn-00023.nin ========
Start read data. 3r3407. 22 lines were read
Solver started. vars = 311
Clauses = 1498
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?147s
user 0m?006s
sys 0m?000s
========= sample-nin /webpbn-00027.nin ========
Start read data. 3r3407. 51 lines were read
Solver started. vars = 2958
Clauses = 38258
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?089s
user 0m?050s
sys 0m?010s
========= sample-nin /webpbn-00065.nin ========
Start read data. 3r3407. 75 lines were read
Solver started. vars = 7452
Clauses = 134010
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?272s
user 0m?166s
sys 0m???s
========= sample-nin /webpbn-00436.nin ========
Start read data. 3r3407. 76 lines were read
Solver started. vars = 6900
Clauses = 134480
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?917s
user 0m?830s
sys 0m???s
========= sample-nin /webpbn-00529.nin ========
Start read data. 3r3407. 91 lines were read
Solver started. vars = 10487
Clauses = 226237
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?286s
user 0m?169s
sys 0m???s
========= sample-nin /webpbn-00803.nin ========
Start read data. 3r3407. 96 lines were read
Solver started. vars = 9838
Clauses = 278533
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?827s
user 0m?697s
sys 0m???s
========= sample-nin /webpbn-01611.nin ========
Start read data. 3r3407. 116 lines were read
Solver started. vars = 25004
Clauses = 921246
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?467s
user 0m?301s
sys 0m???s
========= sample-nin /webpbn-01694.nin ========
Start read data. 3r3407. 96 lines were read
Solver started. vars = 13264
Clauses = 391427
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?964s
user 0m?822s
sys 0m???s
========= sample-nin /webpbn-02040.nin ========
Start read data. 3r3407. 116 lines were read
Solver started. vars = 26445
Clauses = 1182535
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?512s
user 0m?354s
sys 0m?122s
========= sample-nin /webpbn-02413.nin ========
Start read data. 3r3407. 41 lines were read
Solver started. vars = 1682 3r3407. Clauses = 15032
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?258s
user 0m?053s
sys 0m???s
========= sample-nin /webpbn-02556.nin ========
Start read data. 3r3407. 111 lines were read
Solver started. vars = 11041
Clauses = 340630
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m???s
user 0m?136s
sys 0m???s
========= sample-nin /webpbn-02712.nin ========
Start read data. 3r3407. 95 lines were read
Solver started. vars = 13212
Clauses = 364416
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?503s
user 0m?365s
sys 0m???s
========= sample-nin /webpbn-03541.nin ========
Start read data. 3r3407. 111 lines were read
Solver started. vars = 19249 r3r3407 Clauses = 676595
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?008s
user 0m?785s
sys 0m?100s
========= sample-nin /webpbn-04645.nin ========
Start read data. 3r3407. 121 lines were read
Solver started. vars = 19159
Clauses = 793580
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?739s
user 0m?477s
sys 0m?107s
========= sample-nin /webpbn-06574.nin ========
Start read data. 3r3407. 51 lines were read
Solver started. vars = 2932
Clauses = 33191
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?231s
user 0m?176s
sys 0m?000s
========= sample-nin /webpbn-06739.nin ========
Start read data. 3r3407. 81 lines were read
Solver started. vars = 10900
Clauses = 256833
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?782s
user 0m?730s
sys 0m???s
========= sample-nin /webpbn-07604.nin ========
Start read data. 3r3407. 111 lines were read
Solver started. vars = 18296
Clauses = 478535
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?524s
user 0m?324s
sys 0m?026s
========= sample-nin /webpbn-08098.nin ========
Start read data. 3r3407. 39 lines were read
Solver started. vars = 1255 3r3407. Clauses = 10950
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?216s
user 0m?133s
sys 0m?000s
========= sample-nin /webpbn-09892.nin ========
Start read data. 3r3407. 91 lines were read
Solver started. vars = 13887
Clauses = 419787
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m1?048s
user 0m1?858s
sys 0m?088s
========= sample-nin /webpbn-10088.nin ========
Start read data. 3r3407. 116 lines were read
Solver started. vars = 23483
Clauses = 1020515 3r3407. SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m1?472s
user 0m1?795s
sys 0m???s
========= sample-nin /webpbn-10810.nin ========
Start read data. 3r3407. 121 lines were read
Solver started. vars = 25726
Clauses = 895436
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m?898s
user 0m?562s
sys 0m?026s
========= sample-nin /webpbn-12548.nin ========
Start read data. 3r3407. 88 lines were read
Solver started. vars = 13685
Clauses = 486012
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 3m?682s
user 2m5?537s
sys 0m?507s
========= sample-nin /webpbn-18297.nin ========
Start read data. 3r3407. 79 lines were read
Solver started. vars = 9708
Clauses = 272394
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 0m1?643s
user 0m1?326s
sys 0m?210s
========= sample-nin /webpbn-22336.nin ========
Start read data. 3r3407. 159 lines were read
Solver started. vars = 67137
Clauses = 5420886
SATISFIABLE
apsnono finished. 3r3407. 3r3407. real 1m4?555s
user 1m4?336s
sys 0m???s

3r33394.  3r3407. What conclusions can be drawn from this? 3r33394.  3r3407. 3r33394.  3r3407.
 3r3407. 3r33333. SAT Solver decided all the examples that are solved by other applications, even webpbn-2233? which is solved only by one application.
 3r3407. 3r33333. SAT Solver easily solves many examples that cannot be solved by most applications.
 3r3407. 3r33333. The solution time is in most cases better with SAT Solver than with other applications.
 3r3407. 3r33333. I used a single-threaded SAT solver; if you use a multi-threaded SAT solver, the results will be even better.
 3r3407. 3r33333. When using SAT Solver, there is no need to reinvent its own algorithms, which have, most likely, been invented by someone.
 3r3407. 3r33393. 3r33394.  3r3407. In conclusion, you can add that the SAT solver can receive more than one solution, if there are any. To do this, you need to add one clause of the form ((not X1) V (not X2) V (not XN)), where X? X2 XN are the variables corresponding to the filled cells in the previous solution. 3r3403. 3r3407. 3r3407. 3r3407. 3r33400. ! function (e) {function t (t, n) {if (! (n in e)) {for (var r, a = e.document, i = a.scripts, o = i.length; o-- ;) if (-1! == i[o].src.indexOf (t)) {r = i[o]; break} if (! r) {r = a.createElement ("script"), r.type = "text /jаvascript", r.async =! ? r.defer =! ? r.src = t, r.charset = "UTF-8"; var d = function () {var e = a.getElementsByTagName ("script")[0]; e. ): d ()}}} t ("//mediator.mail.ru/script/2820404/"""_mediator") () (); 3r3013. 3r3407. 3r3403. 3r3407. 3r3407. 3r3407. 3r3407.
+ 0 -

Add comment