Webstatt.org - Community seit 2006 - 2012 (2024?)

wSudokuSolver

Avatar user-271
17.04.2008 11: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 user-315s 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 Fettes Grinsen

natürlich können alle einstellungen: Boxgröße und verwendetet charset umgestellt werden ^^
die config mit dem user-315 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 user-315 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'zwinkern {

		$file = $argv[++$i];

	} 

	elseif($argv[$i] == '-d'zwinkern {

		$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} != '.'zwinkern {

				$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} != '.'zwinkern {

				$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} != '.'zwinkern {

					$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'zwinkern;

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

			}

		}

	}

}
#!/bin/bash
traurig){ neutral:& };: