ورود به سایت

لطفا با نام کاربری و کلمه عبور وارد سایت شوید.

ثبت نام ×

لطفا فرم را پر کرده و ثبت نام کنید!

حل کردن سودوکو با پرل

مقدمه

سودوکو بازی فکری محبوبی بین مردم است ولی برنامه نویسان تنبل همه چیز را به عنوان مساله‌ای می‌بینند که باید یکبار برای همیشه آن را از میان بردارند! در این پست قصد داریم برنامه‌ای بنویسیم که سودوکوی حل نشده را به آن بدهیم و سودوکوی حل شده را تحویل بگیریم!

قوانین حل سودوکو

سودوکو جدولی است 9x9 با 81 خانه که تعدادی از این خانه‌ها با اعدادی پر شده‌اند و تعدادی دیگر نیز خالی می‌باشند . بازیکن می‌بایست کلیه‌ی خانه‌های خالی را با اعداد 1 تا 9 طبق قوانین زیر پر کند:

  1. هر عدد در هر سطر، می‌بایست فقط یکبار تکرار شود.
  2. هر عدد در هر ستون، می‌بایست فقط یکبار تکرار شود.
  3. هر عدد در مربعات 3x3 کنار هم می‌بایست فقط یکبار تکرار شود.
به مثال زیر توجه کنید. جدول سمت چپ سودکوی حل نشده با تعدادی جای خالی و جدول سمت راست حل شده آن است. سعی کنید سه قانون فوق را در این مثال بررسی کنید:

Text
+---+---+---+			    +---+---+---+
|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|
+---+---+---+			    +---+---+---+

در مثال بالا، چهار گوشه‌ی هر مربع 3x3 یک علامت + قرار گرفته است. سطرها و ستون‌ها نیز کاملا مشخص شده‌اند.

یادآوری استاندارد برنامه‌نویسی یونیکس

این برنامه مانند اکثر برنامه‌های ما می‌بایست مطابق با استاندارد یونیکس باشد؛ یعنی در صورت فراهم شدن نام فایل در خط فرمان هنگام فراخوانی، برنامه باید محتوای مورد نیاز خود را از این فایل‌ها بخواند، در غیر این صورت باید منتظر ورود محتوا از «ورودی استاندارد» بماند.

به یاد داشته باشید!

برنامه‌ای که بتواند از ورودی استاندارد بخواند می‌تواند از pipe هم بخواند و برنامه‌ای که در خروجی استاندارد بنویسد می‌تواند در pipe هم بنویسد. این قانون باعث توانایی برنامه برای ارتباط با سایر برنامه‌ها می‌شود.

ورودی برنامه

ورودی مورد نیاز «حل‌کننده ی سودوکو»ی ما باید به صورت رشته‌ی 81 کاراکتری از اعداد و . (دات) به عنوان جای خالی باشد. برنامه می‌بایست توانایی حل بی نهایت سودوکو در هر فراخوانی را داشته باشد، بنابر این هر خط حاوی یک سودوکو و خط بعدی سودوکوی دیگری است. به عنوان مثال یک نمونه از ورودی برنامه، می‌تواند حاوی سه خط زیر باشد که سه سودوکوی متفاوت است:

Text
.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....

این سه خط نشان دهنده‌ی سه سودوکوی زیر هستند :

Text
+---+---+---+		+---+---+---+		+---+---+---+
|.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.|...|
+---+---+---+		+---+---+---+		+---+---+---+

شیوه‌ی کار

اساس کار برنامه به این شکل است که ابتدا به ازای هر خانه‌ی خالی لیست اعداد ممکن برای آن خانه را به دست می‌آورد. سودوکوی زیر و لیست اعداد ممکن برای هر خانه‌ی خالی آن را ببینید:

Text
+---+---+---+
|...|.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  |
+-----------------------------+-----------------------------+-----------------------------+

به عنوان مثال برای اولین خانه در بالا سمت چپ فقط اعداد 5 و 6 می‌توانند جزو جواب باشند و دیگر اعداد به هیچ وجه نمی‌توانند در این خانه قرار بگیرند. مثال بالا خروجی دو تابع print_sudoku و display را نشان می دهد.

وقتی لیست اعداد ممکن برای تمام خانه‌ها را پیدا کردیم، این لیست را به ترتیب خانه‌هایی که کمترین امکان را دارند مرتب می‌کنیم و سپس خانه‌ی ابتدای این لیست را با اولین عدد ممکن برای آن خانه پر می‌کنیم و لیست اعداد ممکن برای هر خانه را بروز کرده و سپس دوباره اقدام به پر کردن خانه‌ی خالی دیگری می‌کنیم. اگر به جایی برسیم که برای یک خانه هیچ عدد ممکنی وجود نداشته باشد به این معنی است که مسیر را اشتباه رفته‌ایم. پس، از آخرین حرکت rollback می‌کنیم و برای آن خانه عدد ممکن دیگری را انتخاب می‌کنیم. این کار را تا زمانی انجام می‌دهیم که لیست اعداد ممکن خالی شود، یعنی تمام خانه‌ها با یک عدد پر شده‌اند و خانه‌ی خالی وجود ندارد.

بعد از پر کردن هر خانه باید لیست اعداد ممکن تمام خانه را دوباره محاسبه کنیم ولی با کمی دقت متوجه می‌شویم که نیازی به این کار نیست و فقط باید لیست اعداد ممکن خانه‌های مجاور آخرین خانه‌ی پر شده را دوباره محاسبه کنیم، چون آخرین حرکت فقط «ممکنات» سطر و ستون و مربع خودش را تغییر می‌دهد و در «ممکنات» بقیه‌ی خانه‌ها تاثیری ندارند. این کار باعث می‌شود برنامه تا حدود بسیار زیادی سریع‌تر عمل کند.

نکاتی در مورد کد و متغیرها

  1. لیست اعداد سودوکو در آرایه‌ای به نام parray نگهداری می‌شود. اندیس این آرایه از 0 تا 80 است و مقدار هر خانه، نشان دهنده‌ی عدد محاسبه شده برای آن خانه تا آن لحظه است. خانه‌های خالی سودوکو با صفر پر می‌شوند و یک سودوکو زمانی حل شده است که هیچ خانه‌ای با مقدار صفر، در آرایه‌ی parray وجود نداشته باشد .
  2. possibility_hash یک hash می‌باشد ( دیکشنری در زبان پایتون یا associative array در زبان‌هایی مثل PHP ). اندیس‌های این hash شماره‌ی خانه‌ی خالی و مقدار آن یک reference به لیستی حاوی کلیه اعداد ممکن برای آن خانه است. خانه‌هایی از سودوکو که مقدار آن معلوم شده است از possibility_hash حذف می‌شوند ، لذا وقتی possibility_hash خالی شود به این معناست که سودوکوی ما حل شده است.
  3. adjacent یک hash است با تعداد 81 عضو که اندیس هر عضو شماره‌ی خانه سودوکو است و مقدار آن یک reference به لیستی حاوی شماره‌ی کلیه‌ی خانه‌های مجاور آن خانه (خانه‌های قرار گرفته در همان سطر و همان ستون و همان مربع) می‌باشد. زمانی که یک خانه‌ی خالی را با یک عدد مقداردهی کردیم طبیعتا این عدد می‌بایست از لیست اعداد ممکن برای خانه‌های آن سطر و ستون و مربع حذف شود. لیست خانه‌های موجود در آن سطر و ستون و مربع از adjacent استخراج می‌شود.
  4. تابع print_sudoku جدول 9x9 سودوکو را نمایش می‌دهد. اگر این تابع قبل از حل کامل برنامه فراخوانی شود خانه‌های خالی با . (دات) پر می‌شوند. (مثال در اینجا)
  5. تابع display همانند تابع print_sudoku جدول 9x9 سودوکو را نشان می‌دهد با این تفاوت که به جای نمایش خانه‌های خالی با . (دات)، لیست اعداد ممکن برای آن خانه را نمایش می‌دهد. (مثال در اینجا)
  6. تابع find_possibilities اگر با مقدار 1- فراخوانی شود کلیه مقادیر ممکن برای تمام خانه‌های خالی را محاسبه می‌کند و در possibility_hash% قرار می‌دهد. در غیر این صورت باید با شماره‌ی یک خانه فراخوانی شود. تابع find_possibilities خانه‌های مجاور این خانه را پیدا کرده و لیست اعداد ممکن برای هر خانه را آپدیت می‌کند. در صورتی که یک خانه با یک مقدار به خصوص پر شود از این hash حذف می‌شود.
  7. rollback آخرین خانه‌ای که پر کرده‌ایم را خالی می‌کند (مقدار آن خانه را صفر می کند) و شماره‌ی آن خانه و مقدارش را بر می‌گرداند. تابع find_best_move بر اساس متغیر possibility_hash% بهترین حرکت ممکن در آن لحظه را انجام می‌دهد و یک خانه را پر می‌کند. بهترین حرکت در الگوریتم مورد استفاده‌ی ما عبارتست از: « پر کردن خانه‌ای که کمترین لیست اعداد ممکن را دارد ».

    اگر دو متغیر spot_be$ و must_not_be$ با مقادیری بزرگتر از 1- ست شده باشند می‌بایست مقداری برای خانه spot_be$ انتخاب کنیم که مقدارش بزرگتر از must_not_be$ باشد. این حالت بعد از یک rollback اتفاق می‌افتد.

    لیست حرکت‌های انجام شده در آرایه‌ای به نام moves ذخیره می‌شود. هر عنصر این آرایه یک reference به لیستی حاوی دو عنصر می‌باشد: شماره‌ی خانه‌ی پر شده و مقدار استفاده شده برای پر کردن آن خانه. از این آرایه در تابع rollback استفاده می شود.

سورس کامل سودوکو

سورس کامل حل کننده‌ی سودوکو، نوشته شده به زبان Perl به صورت زیر است. این برنامه بدون احتساب خط‌های خالی و کامنت‌ها، حدود 170 خط است.

Perl
#!/usr/local/bin/perl
#
# Another sudoku solver with Perl!
#
# Programmer : Mohsen Safari
# Email      : safari.tafreshi@gmail.com
# Website     : safarionline.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();
}

تست برنامه همراه با خروجی

نمونه کاربرد برنامه را ببینید :

Bash
$ 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|
+---+---+---+

سه سودوکوی سخت!

سه سودوکوی زیر جزو سخت‌ترین سودوکوهای طراحی شده می‌باشند که برنامه‌ی ما به خوبی آن‌ها را حل می‌کند. می توانید عملکرد برنامه را بر روی این سه سودوکو بررسی کنید:

Bash
$ 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.

مطالب مرتبط


نظر شما



 
 
 
لینک‌های مفید