یادداشت نویسنده
این یادداشت در سال ۱۳۹۳ نوشته و در سایتی دیگر منتشر شده بود. در اردیبهشت ۱۴۰۲ آن را بازبینی کردم و در «دوکاج» بازنشر میشود.
فهرست مطالب
مقدمه🔗
سودوکو بازی فکری محبوبی بین مردم است ولی برنامه نویسان تنبل همه چیز را به عنوان مسالهای میبینند که باید یکبار برای همیشه آن را از میان بردارند! در این پست قصد داریم برنامهای بنویسیم که سودوکوی حل نشده را به آن بدهیم و سودوکوی حل شده را تحویل بگیریم!
قوانین حل سودوکو🔗
سودوکو جدولی است ۹x۹ با ۸۱ خانه که تعدادی از این خانهها با اعدادی پر شدهاند و تعدادی دیگر نیز خالی هستند . بازیکن میبایست کلیهی خانههای خالی را با اعداد ۱ تا ۹ طبق قوانین زیر پر کند:
- هر عدد در هر سطر، میبایست فقط یکبار تکرار شود.
- هر عدد در هر ستون، میبایست فقط یکبار تکرار شود.
- هر عدد در مربعات ۳x۳ کنار هم میبایست فقط یکبار تکرار شود.
به مثال زیر توجه کنید. جدول سمت چپ سودکوی حل نشده با تعدادی خانهی خالی و جدول سمت راست نسخهی حل شدهی آن است. سعی کنید سه قانون فوق را در این مثال بررسی کنید:
+---+---+---+ +---+---+---+
|4..|...|8.5| |417|369|825|
|.3.|...|...| |632|158|947|
|...|7..|...| |958|724|316|
+---+---+---+ +---+---+---+
|.2.|...|.6.| |825|437|169|
|...|.8.|4..| |791|586|432|
|...|.1.|...| |346|912|758|
+---+---+---+ +---+---+---+
|...|6.3|.7.| |289|643|571|
|5..|2..|...| |573|291|684|
|1.4|...|...| |164|875|293|
+---+---+---+ +---+---+---+
در مثال بالا، چهار گوشهی هر مربع ۳x۳ یک علامت + قرار گرفته است. سطرها و ستونها نیز کاملا مشخص شدهاند.
یادآوری استاندارد برنامهنویسی یونیکس🔗
این برنامه مانند اکثر برنامههای ما میبایست مطابق با استاندارد یونیکس باشد؛ یعنی در صورت فراهم شدن نام فایل(هایی) در خط فرمان هنگام فراخوانی، برنامه باید محتوای خود را از این فایل(ها) بخواند، در غیر این صورت باید منتظر ورود محتوا از «ورودی استاندارد» بماند.
به یاد داشته باشید!
برنامهای که بتواند از ورودی استاندارد بخواند میتواند از pipe هم بخواند و برنامهای که در خروجی استاندارد بنویسد میتواند در pipe هم بنویسد. این قانون باعث ارتباط برنامه با سایر برنامهها میشود.
ورودی برنامه🔗
ورودیِ «حلکنندهی سودوکو»ی ما رشتهای ۸۱ کاراکتری از اعداد و .
(دات) به عنوان جای خالی است. این اعداد و جاهای خالی به صورت سطر به سطر در جدول سودوکو قرار میگیرند. برنامه میبایست توانایی حل بینهایت سودوکو در هر فراخوانی را داشته باشد، بنابر این هر خط فایل (یا ورودی) حاوی یک سودوکو و خط بعدی سودوکوی دیگری است. به عنوان مثال، یک نمونه از ورودی برنامه، میتواند حاوی سه خط زیر باشد که سه سودوکوی متفاوت است:
.6.5.4.3.1...9...8.........9...5...6.4.6.2.7.7...4...5.........4...8...1.5.2.3.4.
7.....4...2..7..8...3..8.799..5..3...6..2..9...1.97..6...3..9...3..4..6...9..1.35
....7..2.8.......6.1.2.5...9.54....8.........3....85.1...3.2.8.4.......9.7..6....
این سه خط نشان دهندهی سه سودوکوی زیر هستند :
+---+---+---+ +---+---+---+ +---+---+---+
|.6.|5.4|.3.| |7..|...|4..| |...|.7.|.2.|
|1..|.9.|..8| |.2.|.7.|.8.| |8..|...|..6|
|...|...|...| |..3|..8|.79| |.1.|2.5|...|
+---+---+---+ +---+---+---+ +---+---+---+
|9..|.5.|..6| |9..|5..|3..| |9.5|4..|..8|
|.4.|6.2|.7.| |.6.|.2.|.9.| |...|...|...|
|7..|.4.|..5| |..1|.97|..6| |3..|..8|5.1|
+---+---+---+ +---+---+---+ +---+---+---+
|...|...|...| |...|3..|9..| |...|3.2|.8.|
|4..|.8.|..1| |.3.|.4.|.6.| |4..|...|..9|
|.5.|2.3|.4.| |..9|..1|.35| |.7.|.6.|...|
+---+---+---+ +---+---+---+ +---+---+---+
شیوهی کار🔗
اساس کار برنامه به این شکل است که ابتدا به ازای هر خانهی خالی لیست اعداد ممکن برای آن خانه را به دست میآوریم. سودوکوی زیر و لیست اعداد ممکن برای هر خانهی خالی آن را ببینید:
+---+---+---+
|...|.7.|.2.|
|8..|...|..6|
|.1.|2.5|...|
+---+---+---+
|9.5|4..|..8|
|...|...|...|
|3..|..8|5.1|
+---+---+---+
|...|3.2|.8.|
|4..|...|..9|
|.7.|.6.|...|
+---+---+---+
+-----------------------------+-----------------------------+-----------------------------+
| 56 | 34569 | 3469 | 1689 | 7 | 13469 | 13489 | 2 | 345 |
| 8 | 23459 | 23479 | 19 | 1349 | 1349 | 13479 | 134579 | 6 |
| 67 | 1 | 34679 | 2 | 3489 | 5 | 34789 | 3479 | 347 |
+-----------------------------+-----------------------------+-----------------------------+
| 9 | 26 | 5 | 4 | 123 | 1367 | 2367 | 367 | 8 |
| 1267 | 2468 | 124678 | 15679 | 12359 | 13679 | 234679 | 34679 | 2347 |
| 3 | 246 | 2467 | 679 | 29 | 8 | 5 | 4679 | 1 |
+-----------------------------+-----------------------------+-----------------------------+
| 156 | 569 | 169 | 3 | 1459 | 2 | 1467 | 8 | 457 |
| 4 | 23568 | 12368 | 1578 | 158 | 17 | 12367 | 13567 | 9 |
| 125 | 7 | 12389 | 1589 | 6 | 149 | 1234 | 1345 | 2345 |
+-----------------------------+-----------------------------+-----------------------------+
نکته
مثال بالا خروجی دو تابع print_sudoku
و display
را نشان می دهد.
به عنوان مثال برای اولین خانه در بالا سمت چپ فقط اعداد ۵ و ۶ میتوانند جزو جواب باشند و دیگر اعداد به هیچ وجه نمیتوانند در این خانه قرار بگیرند.
وقتی لیست اعداد ممکن برای تمام خانهها را پیدا کردیم، این لیست را به ترتیبِ خانههایی که کمترین «امکان» را دارند مرتب میکنیم و سپس خانهی ابتدای این لیست را با اولین عدد ممکن برای آن خانه پر میکنیم و لیست اعداد ممکن برای هر خانه را بروز کرده و سپس دوباره اقدام به پر کردن خانهی خالی دیگری میکنیم. اگر به جایی برسیم که برای یک خانه هیچ عدد «ممکن»ی وجود نداشته باشد به این معنی است که مسیر را اشتباه رفتهایم. بنابر این، از آخرین حرکت rollback
میکنیم و برای آن خانه عدد ممکن دیگری را انتخاب میکنیم. این کار را تا زمانی انجام میدهیم که لیست اعداد ممکن خالی شود، یعنی تمام خانهها با یک عدد پر شدهاند و خانهی خالی وجود ندارد.
بعد از پر کردن هر خانه باید لیستِ اعدادِ ممکنِ تمامِ خانهها را دوباره محاسبه کنیم ولی با کمی دقت متوجه میشویم که نیازی به این کار نیست و فقط باید لیست اعداد ممکن خانههای مجاور آخرین خانهی پر شده را دوباره محاسبه کنیم، چون آخرین حرکت فقط «ممکنات» سطر و ستون و مربع خودش را تغییر میدهد و در «ممکنات» بقیهی خانهها تاثیری ندارد. این کار باعث میشود برنامه تا حدود بسیار زیادی سریعتر عمل کند.
نکاتی در مورد کد و متغیرها🔗
-
لیست اعداد سودوکو در آرایهای به نام
parray
نگهداری میشود. اندیس این آرایه از ۰ تا ۸۰ است و مقدار هر خانه، نشان دهندهی عدد محاسبه شده برای آن خانه تا آن لحظه است. خانههای خالی سودوکو با صفر پر میشوند و یک سودوکو زمانی حل شده است که هیچ خانهای با مقدار صفر، در آرایهی parray وجود نداشته باشد. -
possibility_hash
یک hash است (دیکشنری در زبان پایتون یا associative array در زبانهایی مثل PHP). اندیسهای این hash شمارهی خانهی خالی و مقدار آن یک reference به لیستی حاوی کلیه اعداد ممکن برای آن خانه است. خانههایی از سودوکو که مقدار آن معلوم شده است از possibility_hash حذف میشوند، بنابر این وقتی possibility_hash خالی شود به این معناست که سودوکوی ما حل شده است. -
adjacent
یک hash است با تعداد ۸۱ عضو که اندیس هر عضو شمارهی خانه سودوکو است و مقدار آن یک reference به لیستی حاوی شمارهی کلیهی خانههای مجاور آن خانه (خانههای قرار گرفته در همان سطر و همان ستون و همان مربع) است. زمانی که یک خانهی خالی را با یک عدد مقداردهی کردیم طبیعتا این عدد میبایست از لیست اعداد ممکن برای خانههای آن سطر و ستون و مربع حذف شود. لیست خانههای موجود در آن سطر و ستون و مربع از adjacent استخراج میشود. -
تابع
print_sudoku
جدول ۹x۹ سودوکو را نمایش میدهد. اگر این تابع قبل از حل کامل برنامه فراخوانی شود خانههای خالی با . (دات) پر میشوند. (مثال در اینجا) -
تابع
display
همانند تابع print_sudoku جدول ۹x۹ سودوکو را نشان میدهد با این تفاوت که به جای نمایش خانههای خالی با . (دات)، لیست اعداد ممکن برای آن خانه را نمایش میدهد. (مثال در اینجا) -
تابع
find_possibilities
اگر با مقدار 1- فراخوانی شود کلیهی مقادیر ممکن برای تمام خانههای خالی را محاسبه میکند و در possibility_hash% قرار میدهد. در غیر این صورت باید با شمارهی یک خانه فراخوانی شود. تابع find_possibilities خانههای مجاور این خانه را پیدا کرده و لیست اعداد ممکن برای هر خانه را آپدیت میکند. در صورتی که یک خانه با یک مقدار به خصوص پر شود از این hash حذف میشود. -
rollback
آخرین خانهای که پر کردهایم را خالی میکند (مقدار آن خانه را صفر می کند) و شمارهی آن خانه و مقدارش را بر میگرداند. -
تابع
find_best_move
بر اساس متغیر possibility_hash% بهترین حرکت ممکن در آن لحظه را انجام میدهد و یک خانه را پر میکند. بهترین حرکت در الگوریتم مورد استفادهی ما یعنی: «پر کردن خانهای که کمترین لیست اعداد ممکن را دارد». -
اگر دو متغیر
$spot_be
و$must_not_be
با مقادیری بزرگتر از 1- سِت شده باشند میبایست مقداری برای خانه spot_be$ انتخاب کنیم که مقدارش بزرگتر از must_not_be$ باشد. این حالت بعد از یک rollback اتفاق میافتد. -
لیست حرکتهای انجام شده در آرایهای به نام
moves
ذخیره میشود. هر عنصر این آرایه یک reference به لیستی حاوی دو عنصر است: شمارهی خانهی پر شده و مقدار استفاده شده برای پر کردن آن خانه. از این آرایه در تابع rollback استفاده می شود.
سورس کامل سودوکو🔗
سورس کامل حل کنندهی سودوکو، نوشته شده به زبان Perl به صورت زیر است. این برنامه بدون احتساب خطهای خالی و کامنتها، حدود ۱۷۰ خط است.
#!/usr/local/bin/perl
#
# Another sudoku solver with Perl!
#
# Programmer : Mohsen Safari
# Email : safari.tafreshi@gmail.com
# Website : dokaj.ir
#
# read sudoku tables from named file provided at command line
# or read it from standard input.
# each line has one sudoku challenge!
# blank entries must be specified with .(dot) or 0(zero).
# Examples:
#
# 4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
# 52...6.........7.13...........4..8..6......5...........418.........3..2...87.....
# 6.....8.3.4.7.................5.4.7.3..2.....1.6.......2.....5.....8.6......1....
# 48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5....
# ....14....3....2...7..........9...3.6.1.............8.2.....1.4....5.6.....7.8...
#
# Usage:
# $ echo 4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4...... | perl sudoku-solver.pl
# $ perl sudoku-solver.pl file
#
use warnings;
use strict;
my (@parray, @moves, @adjacent, %possibility_hash);
#
# A little house keeping! calculate each row, column, and sqaure indexs
# and finally calculate all adjacent of each entry.
#
{
my (@rindex, @cindex, @sqindex);
my (@r, @c, @sq);
my ($r, $c, $sq);
my (%hash, $j);
# first index of each sqaure.
my @sq_start = (0, 3, 6, 27, 30, 33, 54, 57, 60);
foreach(0 .. 8) {
my @arr;
for(my $iter = $_; $iter <= 80; $iter += 9){
push @arr, $iter;
}
# fill indexes of each column.
$cindex[$_] = [@arr];
# Calculate indexes of each row.
$rindex[$_] = [$_ * 9 .. $_ * 9 + 8];
$j = $sq_start[$_];
# fill indexes of each square
$sqindex[$_] = [$j, $j+1,$j+2,$j+9,$j+10,$j+11,$j+18,$j+19,$j+20];
}
foreach(0 .. 80) {
$r = int($_ / 9);
$c = $_ % 9;
if ($r <= 2) {
if($c <= 2) { $sq = 0 } elsif ($c <= 5) { $sq = 1 } else { $sq = 2}
}
elsif ($r <= 5) {
if($c <= 2) { $sq = 3 } elsif ($c <= 5) { $sq = 4 } else { $sq = 5}
}
else {
if($c <= 2) { $sq = 6 } elsif ($c <= 5) { $sq = 7 } else { $sq = 8}
}
@r = @{$rindex[$r]};
@c = @{$cindex[$c]};
@sq = @{$sqindex[$sq]};
%hash = ();
foreach my $j ((@r, @c, @sq)) {
$hash{$j}++;
}
# fill adjacent indexes of each entry.
$adjacent[$_] = [sort {$a <=> $b} keys %hash];
}
}
#
# print sudoku table is a readable and familar format
#
sub print_sudoku {
print "+---+---+---+", "\n";
for (my $i = 0; $i <= $#parray; $i++) {
if ( $i % 3 == 0) {
print "|";
}
print $parray[$i] != 0 ? $parray[$i] : ".";
print "|\n" if ( ($i + 1) % 9 == 0);
if ( ($i + 1) % 27 == 0) {
print "+---+---+---+", "\n";
}
}
}
#
# Print sudoku table. each entry that has not a specified value
# will be filled with its possible values.
#
sub display {
find_possibilities(-1);
print "+-----------------------------+-----------------------------+-----------------------------+" , "\n";
for (my $i = 0; $i <= $#parray; $i++) {
if ( $i % 9 == 0) {
print "|";
}
if ($parray[$i] != 0) {
print " $parray[$i] |";
}
else {
my $b = $possibility_hash{$i};
my $s = "";
$s .= $_ foreach (@{$b});
$s = " " . $s . " " while length $s < 9;
$s = substr($s, 0, length($s) - 1) if length $s > 9;
print $s, "|";
}
print "\n" if ( ($i + 1) % 9 == 0);
if ( ($i + 1) % 27 == 0) {
print "+-----------------------------+-----------------------------+-----------------------------+" , "\n";
}
}
}
#
# when no progress is available we would rollback to previous move
#
sub rollback {
if (!@moves) {
print STDERR "Moves array is empty!\n";
exit 1;
}
my $r = pop @moves;
$parray[$r->[0]] = 0;
return ($r->[0], $r->[1]);
}
#
# find possibilities of each no valued entries.
#
sub find_possibilities {
my (%hash, @arr, @tmp);
my @iterate = $_[0] == -1 ? (0 .. 80) : @{$adjacent[$_[0]]};
delete @possibility_hash{@iterate};
foreach my $i (@iterate) {
next if $parray[$i] != 0;
%hash = ();
@arr = ();
@tmp = @parray[@{$adjacent[$i]}];
$hash{$_}++ foreach((@tmp));
foreach (1..9) {
push @arr, $_ if not exists $hash{$_};
}
return -1 if !@arr;
$possibility_hash{$i} = [@arr];
}
return 1;
}
#
# find best move at current position
#
sub find_best_move {
my $spot_be = shift;
my $must_not_be = shift;
my (@su, @tmp);
if ($spot_be >= 0) {
foreach(@{$possibility_hash{$spot_be}}) {
return ($spot_be, $_) if $_ > $must_not_be;
}
return (-1, -1);
}
for(my $i = 0; $i <= $#parray; $i++) {
next if $parray[$i] != 0;
push @su, "$i @{$possibility_hash{$i}}";
}
@su = sort { length $a <=> length $b } @su;
foreach my $i (@su){
@tmp = split " ", $i;
for (my $j = 1; $j <= $#tmp; $j++) {
return ($tmp[0], $tmp[$j]) if $tmp[$j] != $must_not_be;
}
}
# if no move is available return (-1, -1) to rollback
return (-1, -1);
}
my ($spot, $value, $try, $last);
my ($spot_be, $must_not_be) = (-1, -1);
#
# while there is a line at standard input or named file...
# each line is a sudoku.
#
while (<>) {
chomp;
if (length != 81) {
print STDERR "Invalid sudoku entry!\n";
next;
}
s/\./0/g;
@parray = split "";
print_sudoku;
display;
$try = 0;
$last = -1;
while (1) {
if (find_possibilities($last) == -1) {
($spot_be, $must_not_be) = rollback;
$last = $spot_be;
next;
}
last if !keys %possibility_hash;
($spot, $value) = find_best_move $spot_be, $must_not_be;
if ($spot == -1 and $value == -1) {
($spot_be, $must_not_be) = rollback;
$last = $spot_be;
next;
}
$parray[$spot] = $value;
push @moves, [$spot, $value];
$spot_be = $must_not_be = -1;
$try = $try + 1;
$last = $spot;
}
print "Moves: $try\n";
print_sudoku;
print "@" x 13, "\n" if !eof();
}
تست برنامه همراه با خروجی🔗
نمونه کاربرد برنامه را ببینید:
$ head -n 1 top95.txt
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
$ head -n 1 top95.txt | perl sudoku-solver
+---+---+---+
|4..|...|8.5|
|.3.|...|...|
|...|7..|...|
+---+---+---+
|.2.|...|.6.|
|...|.8.|4..|
|...|.1.|...|
+---+---+---+
|...|6.3|.7.|
|5..|2..|...|
|1.4|...|...|
+---+---+---+
+-----------------------------+-----------------------------+-----------------------------+
| 4 | 1679 | 12679 | 139 | 2369 | 1269 | 8 | 1239 | 5 |
| 26789 | 3 | 1256789 | 14589 | 24569 | 1245689 | 12679 | 1249 | 124679 |
| 2689 | 15689 | 125689 | 7 | 234569 | 1245689 | 12369 | 12349 | 123469 |
+-----------------------------+-----------------------------+-----------------------------+
| 3789 | 2 | 135789 | 3459 | 34579 | 4579 | 13579 | 6 | 13789 |
| 3679 | 15679 | 135679 | 359 | 8 | 25679 | 4 | 12359 | 12379 |
| 36789 | 456789 | 356789 | 3459 | 1 | 245679 | 23579 | 23589 | 23789 |
+-----------------------------+-----------------------------+-----------------------------+
| 289 | 89 | 289 | 6 | 459 | 3 | 1259 | 7 | 12489 |
| 5 | 6789 | 36789 | 2 | 479 | 14789 | 1369 | 13489 | 134689 |
| 1 | 6789 | 4 | 589 | 579 | 5789 | 23569 | 23589 | 23689 |
+-----------------------------+-----------------------------+-----------------------------+
Moves: 481
+---+---+---+
|417|369|825|
|632|158|947|
|958|724|316|
+---+---+---+
|825|437|169|
|791|586|432|
|346|912|758|
+---+---+---+
|289|643|571|
|573|291|684|
|164|875|293|
+---+---+---+
سه سودوکوی سخت!🔗
سه سودوکوی زیر جزو سختترین سودوکوهای طراحی شدهاند که برنامهی ما به خوبی آنها را حل میکند. میتوانید عملکرد برنامه را بر روی آنها بررسی کنید:
$ cat hardest
8..........36......7..9.2...5...7.......457.....1...3...1....68.85...1...9....4..
..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..
85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.
من محسن هستم؛ برنامهنویس PHP و Laravel و Zend Framework و پایتون و فلسک، ولی بیشتر تمرکزم روی لاراول است. این سایت را اولین بار با فلسک نوشتم ولی بعد تصمیم گرفتم آن را با لاراول نیز پیادهسازی کنم. هم نسخهی فسلک و هم نسخهی لاراول را میتوانید روی گیتهابم پیدا و دانلود کنید.
برای ارتباط با من یا در همین سایت کامنت بگذارید و یا به dokaj.ir(at)gmail.com ایمیل بزنید.
در مورد این مطلب یادداشتی بنویسید.