| View previous topic :: View next topic |
| Author |
Message |
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
 Posted: Wed Oct 19, 2005 2:35 pm Post subject: |
 |
|
| xyzzy wrote: |
Ok, I edited my post to add in your times. How do you solve the contest list with only 29045 constraint propagations when there are more than 29045 empty cells to fill? |
thanks
There is an inner loop that (re)applies the constraint methods until no progress is made. Progress is made when one of the methods solves at least one cell. Each iteration of that loop may solve more than one cell.
Iteration stops when the puzzle is solved or when no progress is made, at which point it backtracks. constraint propagation iteraion counts one round of the inner loop. |
|
| Back to top |
|
 |
| abik
| | Joined: 10 Sep 2005 | | Posts: 18 | | : | | Location: Santa Clara |
Items |
|
| Posted: Thu Oct 20, 2005 12:13 am Post subject: |
|
|
Dear gsf,
Are you sure your 100K set is completely pure? When I use the find-all-solutions search, my solver reports slightly more solutions than puzzles.
Aart
| Code: |
=> sudoku FNBTXYW-1-con.dat
#PUZZLES=100000 #SOLUTIONS=100005
nodes=71333935 clocks=22886153456 secs=7.6560 cpn=320.0 Knps=9317.4
=> sudoku -q FNBTXYW-1-con.dat
#PUZZLES=100000 #SOLUTIONS=100000
nodes=34363612 clocks=11080804848 secs=3.7030 cpn=322.0 Knps=9279.9
|
In particular, this puzzle seems to have six solutions:
| Code: |
=> sudoku -p -s problem.txt
Aart's Sudoku Solver v1.0Beta
PROBLEM:
+---+---+---+
|12.|...|34.|
|.5.|.13|.7.|
|.8.|.42|.6.|
+---+---+---+
|..5|3..|..6|
|...|496|...|
|9..|...|4..|
+---+---+---+
|...|168|...|
|6..|...|7..|
|..4|2..|..5|
+---+---+---+
SOLUTION:
+---+---+---+
|126|857|349|
|459|613|872|
|387|942|561|
+---+---+---+
|745|321|986|
|238|496|157|
|961|785|423|
+---+---+---+
|573|168|294|
|692|534|718|
|814|279|635|
+---+---+---+
SOLUTION:
+---+---+---+
|126|857|349|
|459|613|872|
|387|942|561|
+---+---+---+
|745|381|296|
|238|496|157|
|961|725|483|
+---+---+---+
|573|168|924|
|692|534|718|
|814|279|635|
+---+---+---+
SOLUTION:
+---+---+---+
|126|857|349|
|459|613|872|
|387|942|561|
+---+---+---+
|745|381|926|
|238|496|157|
|961|725|483|
+---+---+---+
|573|168|294|
|692|534|718|
|814|279|635|
+---+---+---+
SOLUTION:
+---+---+---+
|126|785|349|
|459|613|872|
|387|942|561|
+---+---+---+
|745|321|986|
|238|496|157|
|961|857|423|
+---+---+---+
|573|168|294|
|692|534|718|
|814|279|635|
+---+---+---+
SOLUTION:
+---+---+---+
|127|685|349|
|456|913|872|
|389|742|561|
+---+---+---+
|745|321|986|
|238|496|157|
|961|857|423|
+---+---+---+
|573|168|294|
|692|534|718|
|814|279|635|
+---+---+---+
SOLUTION:
+---+---+---+
|126|785|349|
|459|613|278|
|783|942|561|
+---+---+---+
|845|327|196|
|231|496|857|
|967|851|423|
+---+---+---+
|572|168|934|
|698|534|712|
|314|279|685|
+---+---+---+
#PUZZLES=1 #SOLUTIONS=6
nodes=358 clocks=60779132 secs=0.0150 cpn=169774.0 Knps=23.9
|
|
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
|
| Back to top |
|
|
| abik
| | Joined: 10 Sep 2005 | | Posts: 18 | | : | | Location: Santa Clara |
Items |
|
| Posted: Thu Oct 20, 2005 4:04 am Post subject: |
|
|
| Quote: |
two improper puzzles entered my original data somewhere along the line
the bad one above was the first with 6 solutions (as you found)
thanks
|
Dear gsf,
This is exactly why I believe Sudoku solvers should find all solutions (for a “pure” Sudoku puzzle this implies finding the solution and proving that no other solution exists), rather than exploiting the single-solution property for some speed improvements, but that is just my two cents, of course.
Aart |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Thu Oct 20, 2005 4:22 am Post subject: |
|
|
| abik wrote: |
This is exactly why I believe Sudoku solvers should find all solutions (for a “pure” Sudoku puzzle this implies finding the solution and proving that no other solution exists), rather than exploiting the single-solution property for some speed improvements, but that is just my two cents, of course.
Aart |
probably depends on the solver author's interests
in my case improper puzzles are the exception
so they get the non-default option |
|
| Back to top |
|
|
| angusj
Site Admin
 | | Joined: 18 Jun 2005 | | Posts: 406 | | : | |
Items |
|
| Posted: Thu Oct 20, 2005 4:49 am Post subject: |
|
|
| abik wrote: | | that is just my two cents, of course. |
You can add my two cents with yours  |
|
| Back to top |
|
|
| xyzzy
| | Joined: 24 Aug 2005 | | Posts: 80 | | : | |
Items |
|
| Posted: Thu Oct 20, 2005 9:51 am Post subject: |
|
|
| Any definition of a sudoku that you will find state that they have only one solution. When a human solves a sudoku, they don't prove that there is only one solution. For larger sizes like 16x16, the difference between solving a sudoku and verifying that a sudoku is valid is an order of magnitude. Verifying is a totally different problem than solving, one that IMHO is lacking in opportunities for improvement of the algorithm. |
|
| Back to top |
|
|
| abik
| | Joined: 10 Sep 2005 | | Posts: 18 | | : | | Location: Santa Clara |
Items |
|
| Posted: Thu Oct 20, 2005 5:36 pm Post subject: |
|
|
Dear gsf,
I just tried some of the new files and they all look "pure" now. I added a new "impurity" feature that accurately reports the number of puzzles that are not true sudoku puzzles, rather than just comparing #puzzles with #solutions in the end. So for the old file, the output would like as follows.
| Code: |
=> sudoku FNBTXYW-1-con.dat
Aart's Sudoku Solver v1.0Beta
#PUZZLES=100000 #SOLUTIONS=100005 #IMPURE-PUZZLES=1
nodes=71333935 clocks=21933737161 secs=6.4530 cpn=307.0 Knps=11054.4
|
Here is the output for some of the new files (still searching for *all* solutions).
| Code: |
=> sudoku FN-1-con-sym.dat
#PUZZLES=1183 #SOLUTIONS=1183
nodes=269413 clocks=83360468 secs=0.0150 cpn=309.0 Knps=17960.9
=> sudoku FN-2-con.dat
#PUZZLES=28948 #SOLUTIONS=28948
nodes=52061382 clocks=15588646328 secs=5.2030 cpn=299.0 Knps=10006.0
=> sudoku FNBTXYW-1-con-rot.dat
#PUZZLES=141 #SOLUTIONS=141
nodes=45792 clocks=13956208 cpn=304.0
=> sudoku FNBTXYW-1-con.dat
#PUZZLES=100000 #SOLUTIONS=100000
nodes=71333690 clocks=21514254996 secs=7.1870 cpn=301.0 Knps=9925.4
|
|
|
| Back to top |
|
|
| Moschopulus
| | Joined: 12 Aug 2005 | | Posts: 39 | | : | |
Items |
|
| Posted: Sat Oct 22, 2005 11:17 am Post subject: |
|
|
| xyzzy wrote: | | When a human solves a sudoku, they don't prove that there is only one solution. |
I would think that most people solve standard sudokus using the standard deduction rules, and in that case they *are* proving that there is only one solution, as well as finding it. They are showing that the solution is forced by the given clues.
When people use the "uniqueness test" to solve are they not proving the solution is unique. They are assuming that there is one solution, and using that information. |
|
| Back to top |
|
|
| dukuso
| | Joined: 14 Jul 2005 | | Posts: 424 | | : | | Location: germany |
Items |
|
| Posted: Sat Oct 29, 2005 5:21 pm Post subject: |
|
|
| Nick70 wrote: | | dukuso wrote: | | is source available ? |
For the whole program no, sorry, it's still very much work in progress.
However the function you are interested in is just this one:
| Code: | int solve_dancing_links(int max_solutions, int *solution_buffer)
{
struct dancing_column *col, *best_col;
int best_len;
struct dancing_node *node, *n;
int level = 0;
struct dancing_node *choice[CELLS];
int solutions = 0;
forward:
if (dancing_root.right == &dancing_root)
{
if (solutions == 0 && solution_buffer)
{
int i;
for (i = 0; i < level; i++)
{
node = choice[i];
solution_buffer[node->cell] = node->val;
}
}
solutions++;
goto backtrack;
}
for (col = dancing_root.right, best_col = col, best_len = best_col->len; col != &dancing_root; col = col->right)
{
if (col->len < best_len)
{
best_col = col;
best_len = best_col->len;
if (best_len == 0)
break;
}
}
if (best_len == 0)
goto backtrack;
node = best_col->head.down;
unlink_col(best_col);
advance:
choice[level] = node;
n = node->right;
while (n != node)
{
unlink_col(n->column);
n = n->right;
};
level++;
goto forward;
backtrack:
if (level == 0)
return solutions;
level--;
node = choice[level];
best_col = node->column;
n = node->left;
while (n != node)
{
relink_col(n->column);
n = n->left;
};
if (max_solutions && solutions >= max_solutions)
goto quickquit;
node = node->down;
if (node != &best_col->head)
goto advance;
quickquit:
relink_col(best_col);
goto backtrack;
} |
|
one small change:
replace if(best_len==0)break;
by : if(best_len<2)break;
if it helps, please update xxyyzz's last table ! |
|
| Back to top |
|
|
| dukuso
| | Joined: 14 Jul 2005 | | Posts: 424 | | : | | Location: germany |
Items |
|
| Posted: Sun Oct 30, 2005 1:20 pm Post subject: |
|
|
I uploaded a new list of hard 16*16 sudokus here:
http://magictour.free.fr/top46
I also improved my solver's speed i.e. on 16*16s ,
so I need 24.1 sec for these with 2.6GHz, complete search
for all solutions.
top46
------
dukuso2:551.6sec
dukuso3:62.7sec
Please add your benchmarks.
I think, 16*16 is more interesting than 9*9 ! |
|
| Back to top |
|
|
| xyzzy
| | Joined: 24 Aug 2005 | | Posts: 80 | | : | |
Items |
|
| Posted: Tue Nov 01, 2005 9:00 am Post subject: |
|
|
I've made my program a little faster, so here are some updated figures to try to beat:
top95:
xyzzy 0.06078 sec @ P2-400MHz = 24.3 Mcycles (1860 cycles/node)
gsf 0.039993 sec @ P4-2.8GHz = 112 Mcycles
abik 0.1250 sec @ P4-3.4GHz = 425 Mcycles (340 cycles/node)
nick70 0.10 sec @ P4-2.4GHz = 240 Mcycles
dukuso 0.15 sec @ P4-2.6GHz = 390 Mcycles
MontagFTB 0.0939 @ G4-1.67GHz = 157 Mcycles
contest:
xyzzy 0.24936 sec @ P2-400MHz = 99.7 Mcycles (958 c/n)
gsf 0.05999 sec @ P4-2.8GHz = 168 Mcycles
abik .0460 sec @ P4-3.4GHz = 156 Mcycles (348 c/n)
Nick70 0.21 sec @ P4-2.4GHz = 504 Mcycles
dukuso 0.30 sec @ P4-2.6GHz = 780 Mcycles (6842 c/n)
MontagFTB 0.5965 @ G4-1.67GHz = 996 Mcycles
top46 (16x16):
xyzzy 17.03 sec @ P2-400MHz = 6812 Mcycles (5574 c/n)
I'd add dukuso's but I don't understand these times:
| Quote: |
dukuso2:551.6sec
dukuso3:62.7sec
|
|
|
| Back to top |
|
|
| dukuso
| | Joined: 14 Jul 2005 | | Posts: 424 | | : | | Location: germany |
Items |
|
| Posted: Tue Nov 08, 2005 9:44 am Post subject: |
|
|
here is a contest:
http://acm.uva.es/cgi-bin/OnlineJudge?ProblemStat:10957
mine is #10 ("RACK T")
Ranklist (Best Accepted or Presentation Error from each author)
CPU Time Memory Author Source Date (UTC) ID (host)
1 0:00.107 392 Csaba Noszaly C 2005/11/07-21:30:42.816 4108521 (H0)
2 0:00.158 444 Albert Graells Rovira C++ 2005/10/30-13:31:04.853 4084707 (H0)
3 0:00.164 408 :p T.N.N.D. C++ 2005/11/02-03:49:26.518 4093973 (H0)
4 0:00.172 396 Rostislav Rumenov C++ 2005/10/30-09:16:40.518 4083953 (H0)
5 0:00.197 456 Benjamin Hummel C++ 2005/10/30-07:06:16.710 4083576 (H0)
6 0:00.217 440 Cho @ HKUST C 2005/11/02-08:11:32.156 4094728 (H0)
7 0:00.238 448 Emilio J. Garcia T. C++ 2005/11/06-21:13:18.019 4106090 (H0)
8 0:00.309 396 Rodrigo Burgos Dominguez ( Retired :S ) C++ 2005/10/30-04:42:43.541 4083121 (H0)
9 0:00.316 400 Joachim Wulff (little joey) C 2005/10/30-06:41:27.934 4083484 (H0)
10 0:00.324 636 RACK T C 2005/11/05-17:05:56.196 4103482 (H0)
also this contest:
http://acmicpc-live-archive.uva.es/nuevoportal/rankprob.php?p=3285
I'm 3 times slower than the best. Well on many-solution-problems
we already saw that my solver can be slow.
and also:
http://acm.uva.es/cgi-bin/OnlineJudge?ProblemStat:10893
the 0.045 seconds here are a mystery ! |
|
| Back to top |
|
|
| torarin
| | Joined: 10 Nov 2005 | | Posts: 1 | | : | |
Items |
|
| Posted: Thu Nov 10, 2005 7:52 pm Post subject: |
|
|
Hi, until now i've only been reading this forum, but now i've got to join in on the discussion! I've been comparing my solver to yours, and here are my times:
Abik's puzzle:
Grids: 1
Solutions: 957263
Nodes: 11432658
Clocks: 8232484684
Time: 3.17421
C/n: 720.085
Top95
Grids: 95
Solutions: 95
Nodes: 85881
Clocks: 152978376
Time: 0.0589842
C/n: 1781.28
Top1011
Grids: 1011
Solutions: 1011
Nodes: 164660
Clocks: 407451440
Time: 0.157102
C/n: 2474.5
I have P4 2,6 GHz, the solver is written in C++ and goes through all solutions. The code is heavily based on Knuth's dancing links solver, and very much resembles the code Abik posted. Yet, his code goes through alot more nodes alot faster than most of us. The pruning he does with dancing links should be enough to get a much lower node count, and I can't see how he could remove anything in that algorithm without slowing it greatly. Does this make sense to anyone? |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Wed Nov 30, 2005 2:22 pm Post subject: |
|
|
the input puzzles are simple enough for just F constraints (only candidate value in cell) to handle
my results (problem rank memory author language submission)
| Code: |
3285 #1 0.061 Minimum Moe Howard C 2005-11-14 15:18:17
10893 #1 0:00.043 64 20814 C 2005/11/16-06:47:25.311
10957 #1 0:00.040 64 20814 C 2005/11/14-07:02:28.664
|
|
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
