Willkommen in der Webstatt Zum Webstatt Blog und Stories
nuit nuit am 17.04.08 13:32

wSudokuSolver v0.1
Beispiel: http://demo.moonsword.info/sudoku/sudoku.php

Ich hab mal vor längerer Zeit einen Sudokusolver geschrieben....das Lustige daran ist, der kommt mit jedem Sudoku zurecht.

das ganze hab ich mal zu einer klasse zusammengefasst.

Es ist ein Konsolenscript.

Bisher hab ich es mit 16x16 und normalen 9x9 sudokus getestet und funktioniert wunderbar, der Algo ist zwar nohc nicht perfekt und er braucht bei den 16x16 Sudokus noch 2h ^^ aber noja...er löst sie, demnach ist das ganz gut :D

natürlich können alle einstellungen: Boxgröße und verwendetet charset umgestellt werden ^^
die config mit dem sudoku sieht beispielsweise so aus:

sudoku.1
9,9,3,3
123456789
1.......4....1.38.27.9.4...91.7...........5..86.4.5.9..3......8..9....2.4.......7


Gesamthöhe,Gesamtbreite,boxhöhe,boxbreite
Charset
Sudoku von Links nach rechts in Zeilen


Das Sudoku wird in dieser einzeiligen Form auch an die klasse übergeben, während das Charset ein array ist und die Boxgröße über eine methode einzeln bestimmt wird
für jedes sudoku muss ein neues objekt angelegt werden ^^

wer fragen hat, soll sich mal das script durchschauen, ich habs ja sogar dokumentiert

./sudoku
#!/usr/bin/php -q
<?php
set_time_limit(0);

include 'Sudoku.class.php';

$start = time();

$debug = false;
$file = '';
for($i = 0; $i < count($argv); $i++) {
if($argv[$i] == '-f') {
$file = $argv[++$i];
}
elseif($argv[$i] == '-d') {
$debug = true;
}
}

if(empty($file) or !is_file($file)) {
print "WARNING: Input file is missing or is not a file\n\n";
die();
}

$fh = file($file);
$sudoku = trim($fh[2]);
$opt = explode(',',trim($fh[0]));
$charset = str_split(trim($fh[1]));

$o = new Sudoku($sudoku);
$o->setdebug = $debug;
print "Setting Configs....\n";
print "Sudoku Information: ".implode(',',$opt)."\n";
print "Using Charset: ".implode(',',$charset)."\n";
$o->setCharset($charset);
$o->setSudoku($opt[0],$opt[1],$opt[2],$opt[3]);
print "\n";
print "Input Sudoku: \n";
$o->printSudoku();
print "\n";
print "Start Solving......";
$start = time();
$solve = $o->solve();
$end = time();
print "DONE\n";

print "\nSolved in ".($end-$start)." secs\n\n";
$o->printSudoku();


das ganze basiert auf einer klasse.

Sudoku.class.php
<?php
class Sudoku {
private $charset = array(1,2,3,4,5,6,7,8,9); # = range(0,9);
private $sudoku = array(
'x' => 9,
'y' => 9,
'boxX' => 3,
'boxY' => 3
);
private $sud;
private $holes = array();
public $emptyHole = '.';
public $setdebug = false;


function __construct($sud) {
$this->sud = $sud;
// Determine all holes where a number is missing
for($i = 0; $i < strlen($sud); $i++) {
if($sud{$i} == $this->emptyHole) {
$this->holes[] = $i;
}
}
}

public function solve($layer=0) {
// Get all Possible Chars for the hole
$possibleChars = $this->_getChars($this->holes[$layer]+1);
$this->debug();

// Get through every Char
foreach($possibleChars as $char) {
$this->sud{$this->holes[$layer]} = $char;
// If the actual hole isn't the last one, recursiv
if($layer != count($this->holes)-1) {
if($this->solve($layer+1)) {
return $this->sud;
}
} else {
return $this->sud;
}
}
$this->sud{$this->holes[$layer]} = '.';
return false;
}

public function setCharset($array) {
$this->charset = $array;
}

public function setSudoku($x,$y,$boxX,$boxY) {
$this->sudoku['x'] = $x;
$this->sudoku['y'] = $y;
$this->sudoku['boxX'] = $boxX;
$this->sudoku['boxY'] = $boxY;
}

private function _getChars($position) {
$row = ceil($position/$this->sudoku['x']);
$column = $position-$row*$this->sudoku['x']+$this->sudoku['x'];

$boxrow = ceil($row/$this->sudoku['boxX']);
$boxcolumn = ceil($column/$this->sudoku['boxY']);

return array_intersect($this->_checkBox($boxrow,$boxcolumn),$this->_checkRow($row),$this->_checkColumn($column));
}

private function _checkRow($row) {
$vorkommen = array();
for($i = $row*$this->sudoku['x']-$this->sudoku['x']; $i < $row*$this->sudoku['x']; $i++) {
if($this->sud{$i} != '.') {
$vorkommen[] = $this->sud{$i};
}
}

return array_diff($this->charset,$vorkommen);
}

private function _checkColumn($column) {
$vorkommen = array();
for($i = $column-1; $i < $this->sudoku['x']*$this->sudoku['y']; $i += $this->sudoku['x']) {
if($this->sud{$i} != '.') {
$vorkommen[] = $this->sud{$i};
}
}
return array_diff($this->charset,$vorkommen);
}

private function _checkBox($boxrow,$boxcolumn) {
$vorkommen = array();
$startbox = ($boxrow*$this->sudoku['boxY']*$this->sudoku['x'])-$this->sudoku['boxY']*$this->sudoku['x']+$this->sudoku['boxY']*$boxcolumn-$this->sudoku['boxY'];

for($a = 0; $a < $this->sudoku['boxY']; $a++) {
for($i = 0; $i < $this->sudoku['boxX']; $i++) {
if($this->sud{$i+$startbox} != '.') {
$vorkommen[] = $this->sud{$i+$startbox};
}
if($startbox+$this->sudoku['boxX'] === $startbox+$i+1) {
$startbox += $this->sudoku['x'];
}
}
}

return array_diff($this->charset,$vorkommen);
}

private function debug($text=false) {
if($this->setdebug) {
if(!$text) {
sleep(1);
exec('clear');
$this->printSudoku();
} else {
print $text."\n";
}
}
}

public function printSudoku() {
print "\n";
$a = 0;
for($i = 0; $i < strlen($this->sud); $i++) {
print str_replace('.',$this->emptyHole,$this->sud{$i})." ";
if(($i+1) % $this->sudoku['boxX'] === 0) {
print " ";
}
if(($i+1) % $this->sudoku['x'] === 0) {
print "\n";
if(($a+1) % $this->sudoku['boxY'] === 0) {
print "\n";
}
$a++;
}
}
}
}

netcup.de Warum gibt es hier Werbung?
Creative Commons Lizenzvertrag
Alle Inhalte des Webstatt-Archivs stehen unter einer Creative Commons Namensnennung - Weitergabe unter gleichen Bedingungen 3.0 Unported Lizenz.

Impressum & Kontakt