#!/usr/bin/perl -w
#
use strict;
use warnings;
use Digest::MD5;
use lib '.';
use Sudoku::PatternSolver qw( :all );
$MAX_SOLUTIONS = 2;
$VERBOSE = 0;
$SOLVE_EMPTY_GIVENS = 0;
$CHEAT_MODE = 1;
# output of 'lscpu | grep Model.name': Intel(R) Xeon(R) CPU E3-1226 v3 @ 3.30GHz
my @A = qw(
5 3 0 0 2 4 7 0 0
0 0 2 0 0 0 8 0 0
1 0 0 7 0 3 9 0 2
0 0 8 0 7 2 0 4 9
0 2 0 9 8 0 0 7 0
7 9 0 0 0 0 0 8 0
0 0 0 0 3 0 5 0 6
9 6 0 0 1 0 3 0 0
0 5 0 6 9 0 0 1 0
);
my $res;
# $res = solve([split //, '.......1......2..3...4...........5..4.16.......71......5....2......8..4..3.91....']);
# $res = solve($ARGV[0] || '1..2..3..2..3..4..3..4..5..4..5..6.............3..4..5..4..5..6..5..6..7..6..7..8');
# $res = solve(\@A);
#exit 0;
#my $puzzlefilename = './HardestDatabase110626.txt';
my ($expectedCount, $puzzlefilename, $solutionfilename);
#($expectedCount, $puzzlefilename, $solutionfilename) = ('49151' , './all_17_clue_sudokus.txt', './all_17_clue_sudokus.solutions.txt');
#($expectedCount, $puzzlefilename, $solutionfilename) = ('10000' , './hard_sudokus.txt', './hard_sudokus.solutions.txt');
#($expectedCount, $puzzlefilename, $solutionfilename) = ('375' , './HardestDatabase110626.txt', './HardestDatabase110626.solutions.txt');
($expectedCount, $puzzlefilename, $solutionfilename) = ('10000' , './tdoku/data/puzzles7_serg_benchmark', './puzzles7_serg.solutions.txt');
#$solutionfilename = './any_sols.txt';
open my $puzz, '<', $puzzlefilename or die "Could not open $puzzlefilename\n";
open my $sols, '>:raw', $solutionfilename or die "Could not open $solutionfilename\n";
print $sols "$expectedCount\n";
my $cnt = 0;
my $solved = 0;
my $start = Time::HiRes::time();
while (<$puzz>) {
/^([\d.]{81})/ or next;
#print $1, "\n";
$cnt++;
# try to specifically address puzzles with 8 symbols
# my $symcnt = 0;
# foreach my $sym (1..9) {
# $symcnt++ if /$sym/;
# }
# next unless $symcnt == 8;
$res = solve($1);
my $solutions = $res->{solutionCount};
if ($solutions) {
$solved++;
print $sols $1, ',', $res->{solutions}[0], "\n";
}
my $time = $res->{seconds};
printf "#%4d: %d solution took %0.6f secs (cheat gave %d clues%s)\n", $cnt, $solutions, $time, $res->{cheatFilled}, ($res->{cheatSolved} ? ' and solved' : '');
#last if $cnt == 10;
}
close $puzz;
close $sols;
my $time = Time::HiRes::time() - $start;
$cnt and printf "%d out of %d sudokus from '%s' were solved in %0.6f secs (avg %0.6f secs), (CHEAT:%s)\n", $solved, $cnt, $puzzlefilename, $time, $time / $cnt, ($CHEAT_MODE ? 'ON' : 'OFF');
open $sols, '<', $solutionfilename or die "Could not open $solutionfilename\n";
binmode $sols;
print "MD5: ", Digest::MD5->new->addfile($sols)->hexdigest, "\n";
exit 0;
# solving the 49151 sudokus took me 312 min (5 1/4 h) and even the md5 sum is incorrect :((
#49146: 1 solution took 0.723708 secs (cheat gave 5 clues)
#49147: 1 solution took 0.427861 secs (cheat gave 3 clues)
#49148: 1 solution took 0.443590 secs (cheat gave 3 clues)
#49149: 1 solution took 0.374147 secs (cheat gave 1 clues)
#49150: 1 solution took 0.479577 secs (cheat gave 4 clues)
#49151: 1 solution took 0.458076 secs (cheat gave 4 clues)
#49151 out of 49151 sudokus from './all_17_clue_sudokus.txt' were solved in 18710.816847 secs (avg 0.380680 secs), (CHEAT:ON)
#MD5: 3f7cf70d393fc04eab8d45683d50e29e
#steffen@Delle-Precision-T1700:~/Projects/sudokusolver$ md5sum all_17_clue_sudokus.solutions.txt
#3f7cf70d393fc04eab8d45683d50e29e all_17_clue_sudokus.solutions.txt
# now I see, in the solutions all zero values should be replaced with the 1 missing symbol (can be any of 1-9)
# same with
#9996: 1 solution took 0.021755 secs (cheat gave 5 clues)
#9997: 1 solution took 0.028629 secs (cheat gave 8 clues)
#9998: 1 solution took 0.032346 secs (cheat gave 5 clues)
#9999: 1 solution took 0.038220 secs (cheat gave 7 clues)
#10000: 1 solution took 0.027387 secs (cheat gave 10 clues)
#10000 out of 10000 sudokus from './hard_sudokus.txt' were solved in 348.971500 secs (avg 0.034897 secs), (CHEAT:ON)
#MD5: 71c523acf117f6b13390ff8b0695bb61
# 96: 1 solution took 0.080372 secs (cheat gave 13 clues)
# 97: 1 solution took 0.161507 secs (cheat gave 13 clues)
# 98: 1 solution took 0.388220 secs (cheat gave 7 clues)
# 99: 1 solution took 0.236333 secs (cheat gave 6 clues)
# 100: 1 solution took 0.703402 secs (cheat gave 6 clues)
#100 out of 100 sudokus from './all_17_clue_sudokus.txt' were solved in 50.571030 secs (avg 0.505710 secs), (CHEAT:ON)
# 96: 1 solution took 0.611017 secs (cheat gave 0 clues)
# 97: 1 solution took 1.650456 secs (cheat gave 0 clues)
# 98: 1 solution took 1.007266 secs (cheat gave 0 clues)
# 99: 1 solution took 0.525731 secs (cheat gave 0 clues)
# 100: 1 solution took 1.411640 secs (cheat gave 0 clues)
#100 out of 100 sudokus from './all_17_clue_sudokus.txt' were solved in 132.478995 secs (avg 1.324790 secs), (CHEAT:OFF)
# cheat mode : ON
#372: 1 solution took 0.578105 secs
#373: 1 solution took 0.525141 secs
#374: 1 solution took 0.244927 secs
#375: 1 solution took 0.234053 secs
#375 out of 375 sudokus from './HardestDatabase110626.txt' were solved in 206.062992 secs (avg 0.549501 secs)
# cheat mode : OFF (a tiny bit faster on average)
#372: 1 solution took 0.608786 secs
#373: 1 solution took 0.668110 secs
#374: 1 solution took 0.258524 secs
#375: 1 solution took 0.303995 secs
#375 out of 375 sudokus from './HardestDatabase110626.txt' were solved in 202.061775 secs (avg 0.538831 secs), (CHEAT:OFF)
# the hardest sudoku, according to http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539.html
# '12.4..3..3...1..5...6...1..7...9.....4.6.3.....3..2...5...8.7....7.....5.......98'
#Solution #1 after 0.481312 secs:
#-------------------------
#| 1 2 8 | 4 6 5 | 3 7 9 |
#| 3 7 4 | 2 1 9 | 8 5 6 |
#| 9 5 6 | 8 3 7 | 1 4 2 |
#-------------------------
#| 7 6 5 | 1 9 8 | 4 2 3 |
#| 2 4 9 | 6 7 3 | 5 8 1 |
#| 8 1 3 | 5 4 2 | 9 6 7 |
#-------------------------
#| 5 9 2 | 3 8 6 | 7 1 4 |
#| 4 8 7 | 9 2 1 | 6 3 5 |
#| 6 3 1 | 7 5 4 | 2 9 8 |
#-------------------------
#Exhaustive search took 0.596978 secs and produced 1 solution(s).
#
# '1..2..3..2..3..4..3..4..5..4..5..6.............3..4..5..4..5..6..5..6..7..6..7..8' test case: in cheatmode this should skip pattern solving
# '1...2...3.4.............21....2...3..2....5..5...13.4..1..34...3...5....2.......5' by '53x15', only 5 different clues, one solution when pattern solving, 24 otherwise
# '1472.836.2.836.47136.471.82471.826.3.826.37146.371482.71482..3682..36147.361472.8' try to find a well-posed puzzle with <8 different given values
# '1.72.836.2.836..7136..71.82.71.826.3.826.371.6.371.82.71.82..3682..361.7.361.72.8' has 6 givens and 2 solutions
# '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......' very hard, takes long
# '.....6....59.....82....8....45........3........6..3.54...325..6..................' underdeterminated: 7 values! messes my program up. It's the 'hardest' from http://norvig.com/sudoku.html
# last output on my dell desktop before the process was killed by system after running a couple of hours:
#keystore at 3540000 first solutions + 3539999 rejected as copies = 7079999,
#size: 683068976, total_size: 768028976
#Avg storage size = 108.48 B / key
#Killed
# thus we know there are > 3.5 million different solutions (and I forgot to take the size of the array with stored solutions themselves into account, it's only the keystore)
# I don't know how many more solutions would be there, but the equal number of unique first solutions and immediately follwing rejected copy strongly suggests
# there never is more than 1 pair of two patterns to fill a certain congruent space of 18 free cells. (try to prove!)
use Data::Dumper;
if (0) {
foreach my $sol (@{$res->{solutions}}) {
# print Dumper($sol);
print "'", @$sol, "':";
print_solution($sol);
}
}
printf "Exhaustive search took %0.6f secs and produced %d solution(s).\n", $res->{seconds}, $res->{solutionCount};
#use Games::Sudoku::CPSearch;
#use Games::Sudoku::Solver;
__END__
A puzzle with 6 symbols fully given which has 2 different solutions
C:\Users\Heinrich\scripts\Sudoku-Solver-Project>solve.pl 1.72.836.2.836..7136..71.82.71.826.3.826.371.6.371.82.71.82..3682..361.7.361.72.8
-------------------------
| 1 . 7 | 2 . 8 | 3 6 . |
| 2 . 8 | 3 6 . | . 7 1 |
| 3 6 . | . 7 1 | . 8 2 |
-------------------------
| . 7 1 | . 8 2 | 6 . 3 |
| . 8 2 | 6 . 3 | 7 1 . |
| 6 . 3 | 7 1 . | 8 2 . |
-------------------------
| 7 1 . | 8 2 . | . 3 6 |
| 8 2 . | . 3 6 | 1 . 7 |
| . 3 6 | 1 . 7 | 2 . 8 |
-------------------------
For symbol '1' (9 givens) the pattern is fixed
For symbol '2' (9 givens) the pattern is fixed
For symbol '3' (9 givens) the pattern is fixed
For symbol '6' (9 givens) the pattern is fixed
For symbol '7' (9 givens) the pattern is fixed
For symbol '8' (9 givens) the pattern is fixed
For symbol 'A' (0 givens) 46656 patterns were found, of which 9 were kept (46647 omitted) in 0.223566 secs
For symbol 'B' (0 givens) 46656 patterns were found, of which 6 were kept (46650 omitted) in 0.422191 secs
For symbol 'C' (0 givens) 46656 patterns were found, of which 6 were kept (46650 omitted) in 0.399748 secs
2nd elimination of pattern candidates:
For symbol '1' (9 givens) of 1 patterns initially accepted, of which 1 were kept ( 0 omitted) in 0.000038 secs
For symbol '2' (9 givens) of 1 patterns initially accepted, of which 1 were kept ( 0 omitted) in 0.000043 secs
For symbol '3' (9 givens) of 1 patterns initially accepted, of which 1 were kept ( 0 omitted) in 0.000041 secs
For symbol '6' (9 givens) of 1 patterns initially accepted, of which 1 were kept ( 0 omitted) in 0.000038 secs
For symbol '7' (9 givens) of 1 patterns initially accepted, of which 1 were kept ( 0 omitted) in 0.000035 secs
For symbol '8' (9 givens) of 1 patterns initially accepted, of which 1 were kept ( 0 omitted) in 0.000034 secs
For symbol 'A' (0 givens) of 9 patterns initially accepted, of which 6 were kept ( 3 omitted) in 0.000098 secs
For symbol 'B' (0 givens) of 6 patterns initially accepted, of which 6 were kept ( 0 omitted) in 0.000051 secs
Start with backtracking to find possible combination(s) of patterns after 1.07795 secs:
Solution #1 after 1.079486 secs:
-------------------------
| 1 A 7 | 2 B 8 | 3 6 C |
| 2 C 8 | 3 6 A | B 7 1 |
| 3 6 B | C 7 1 | A 8 2 |
-------------------------
| A 7 1 | B 8 2 | 6 C 3 |
| C 8 2 | 6 A 3 | 7 1 B |
| 6 B 3 | 7 1 C | 8 2 A |
-------------------------
| 7 1 A | 8 2 B | C 3 6 |
| 8 2 C | A 3 6 | 1 B 7 |
| B 3 6 | 1 C 7 | 2 A 8 |
-------------------------
Solution #2 after 1.098755 secs:
-------------------------
| 1 A 7 | 2 B 8 | 3 6 C |
| 2 B 8 | 3 6 C | A 7 1 |
| 3 6 C | A 7 1 | B 8 2 |
-------------------------
| A 7 1 | B 8 2 | 6 C 3 |
| B 8 2 | 6 C 3 | 7 1 A |
| 6 C 3 | 7 1 A | 8 2 B |
-------------------------
| 7 1 A | 8 2 B | C 3 6 |
| 8 2 B | C 3 6 | 1 A 7 |
| C 3 6 | 1 A 7 | 2 B 8 |
-------------------------
Exhaustive search took 1.118176 secs and brought 2 solution(s).
Solution #1
-------------------------
| . A . | . B . | . . C |
| . C . | . . A | B . . |
| . . B | C . . | A . . |
-------------------------
| A . . | B . . | . C . |
| C . . | . A . | . . B |
| . B . | . . C | . . A |
-------------------------
| . . A | . . B | C . . |
| . . C | A . . | . B . |
| B . . | . C . | . A . |
-------------------------
Solution #2
-------------------------
| . A . | . B . | . . C |
| . B . | . . C | A . . |
| . . C | A . . | B . . |
-------------------------
| A . . | B . . | . C . |
| B . . | . C . | . . A |
| . C . | . . A | . . B |
-------------------------
| . . A | . . B | C . . |
| . . B | C . . | . A . |
| C . . | . A . | . B . |
-------------------------
Solution #1 Patterns:
------------------------- ------------------------- -------------------------
| . 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 . | . . . |
------------------------- ------------------------- -------------------------
Solution #2 is made from 3 entirely different Patterns:
------------------------- ------------------------- -------------------------
| . 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 . . | . . . | . . . |
------------------------- ------------------------- -------------------------