世界一難しい数独がどれくらい難しいか解かせてみた

perl

本当に解ける人いるの？　フィンランド人数学者が作った “世界一難しい数独” が発表される | ロケットニュース24


フィンランド人数学者の Arto Inkala さんが今年も世界一難しい数独を発表していたので、CPANモジュール Games::Sudoku::Solver に解かせてみました。


一昨年発表のものはこちら。


Inkalaさんが一昨年発表した問題

$ ./sudoku.pl sudoku_most_difficult2011.txt
sudoku_most_difficult2011.txt

===== Sudoku =====
 0 0 5 3 0 0 0 0 0
 8 0 0 0 0 0 0 2 0
 0 7 0 0 1 0 5 0 0
 4 0 0 0 0 5 3 0 0
 0 1 0 0 7 0 0 0 6
 0 0 3 2 0 0 0 8 0
 0 6 0 5 0 0 0 0 9
 0 0 4 0 0 0 0 3 0
 0 0 0 0 0 9 7 0 0

23 cells occupied, 58 cells free

--- solution 1 ---
（ひみつ）

[time] 1.0258446 (sec)

数時間集中して頑張ればなんとか解けるレベル。


今年の分

$ ./sudoku.pl sudoku_most_difficult2012.txt
sudoku_most_difficult2012.txt

===== Sudoku =====
 8 0 0 0 0 0 0 0 0
 0 0 3 6 0 0 0 0 0
 0 7 0 0 9 0 2 0 0
 0 5 0 0 0 7 0 0 0
 0 0 0 0 4 5 7 0 0
 0 0 0 1 0 0 0 3 0
 0 0 1 0 0 0 0 6 8
 0 0 8 5 0 0 0 1 0
 0 9 0 0 0 0 4 0 0

21 cells occupied, 60 cells free

--- solution 1 ---
（ひみつ）

[time] 27.8268216 (sec)


1 sec（2010） => 27.8 sec (2012)
自分でもざっとやってみましたが、一昨年のと違って初期値で確定できるところがありません。仮定値を置いて進めては出戻り、また別の場所に置いては出戻りでの繰り返しで、自宅や通勤電車のすきま時間ではとても無理。山にこもるしかないレベル。

完敗。

ソースコードはこちら

#!/usr/bin/perl

use strict;
use warnings;
use Games::Sudoku::Solver qw(:Minimal set_solution_max count_occupied_cells sudoku_read);
use Time::HiRes qw(gettimeofday tv_interval);

#引数チェック
my $argc = @ARGV;
if($argc < 1){ exit; }
my $sudoku_file =  $ARGV[0];
print $sudoku_file."\n";

my @sudoku;                                     # the Sudoku data structure
my @solution;                                   # the solution data structure

sudoku_read( \@sudoku, $sudoku_file );           # convert raw to internal representation

print "\n===== Sudoku =====\n";
sudoku_print( \@sudoku );                       # print the Sudoku


my  $cells_occupied = count_occupied_cells( \@sudoku ); # some statistics
print "\n", $cells_occupied, " cells occupied, ",
         81-$cells_occupied, " cells free\n";

set_solution_max(4);                            # stop having 4 solutions found

my $solutions;
#計測開始
my $t0 = [gettimeofday];

#5回測った平均値を出力する
for(my $i=0; $i<5; $i++){
  $solutions = sudoku_solve( \@sudoku, \@solution);    # solve the Sudoku
}

#計測終了(sec)
my $elasped = tv_interval($t0) / 5;     # 平均値(5)

#解が複数ある場合はすべてを出力
foreach my $n ( 1..$solutions ) {               # print the solutions
    print "\n--- solution $n ---\n";
    sudoku_print( $solution[$n-1] );
}
print "[time] $elasped (sec)\n";