Scripts
Sudoku Oplosser
Een maat van me ging een sudoku oplosser in excel bouwen, zonder macro's!?! Ik dacht, die is gek, en wilde hem dus even aftroeven. Ik heb dit in een paar uurtjes in elkaar gezet, en daarna nog een paar uurtjes enige functionaliteit toegevoegd. Helaas wel wat snel gecode, hierdoor weinig commentaar erin. Wellicht dat een volgende versie dit wel bevat. Daarnaast lukt masterclass sudoku nog niet, hiervoor moet er een tijdelijke aanname gedaan worden. Deze functie wil ik op een rustig moment in mijn leven ooit nog eens toevoegen. Wat kan deze class? Los de sudoku op: ->Solve() Zet een waarde: ->SetValue($row, $column, $value) Verkrijg een veldwaarde ->GetValue($row, $column) Verkrijg de complete interne array ->GetAllValues() // Geeft array terug: array( array(rij één waardes), array(rij twee waardes)...) Verkrijg moeilijkheidsgraad: ->GetDifficulty() // Dit is een schatting, hoeveel er door de oplossingen geloopd moest worden, beschikbaar na uitvoeren van ->Solve() Is de sudoku geldig, geen dubbele waarden: ->IsValid() Is de sudoku opgelost? ->IsSolved() Hoeveel velden zijn er ingevuld? ->GetDefined() Opmerking, de versie staat 5 bij. Er zijn een paar private keywords aanwezig, wanneer deze verwijderd worden, draait het script net zo mooi op php4. Het script draait bij mij thuis ivm rekenintensieve taken (alhoewel, binnen een seconde kan ie m toch wel oplossen). Ben je te lui om de sudoku zelf in te vullen in het voorbeeld: Klik hier
sudoku-oplosser
[b]Voorbeeldcode:[/b]
[code]
<html>
<head>
<style>
input.cell{
font-size:16px;
width:40px;
height:40px;
border:1px solid #000000;
}
</style>
</head>
<body>
<?
if(isset($_GET['sudoku']) && isset($_GET['solve'])){
$oSudoku = new Sudoku();
for($row=0; $row<9; $row++){
for($column=0; $column<9; $column++){
if(!empty($_GET['sudoku'][$row][$column]) && !stristr($_GET['sudoku'][$row][$column], ',') ){
$oSudoku->SetValue($row, $column, $_GET['sudoku'][$row][$column]);
}
}
}
$blnInput = $oSudoku->Solve();
if($blnInput === false){
echo '<span style="font-size:18; color:#990000; font-weight:bold;">Fout in ingegeven data!</span><br/>';
}
if( $oSudoku->IsSolved() ){
echo '<span style="font-size:18; color:#009900; font-weight:bold;">Sudoku opgelost!</span>';
}
echo '<form action="?" method="get">Oplossen? <input type="checkbox" name="solve" value="true" checked/> (Wanneer niet geklikt, wordt er slechts een link gegenereerd)<br />Moeilijkheidsgraad:'.$oSudoku->GetDifficulty();
echo '<br/><table>'."\n";
for($row=0; $row<9; $row++){
echo '<tr>'."\n";
for($column=0; $column<9; $column++){
$strStyle = '';
if(($column+1)%3 == 0){
$strStyle .= 'border-right:2px solid #000000; ';
}
if(($row+1)%3 == 0){
$strStyle .= 'border-bottom:2px solid #000000; ';
}
$rowCellVal = $oSudoku->GetValue($row, $column);
if( !is_array($rowCellVal) ){
echo '<td style="'.$strStyle.'"><input class="cell" type="text" name="sudoku['.$row.']['.$column.']" size="2" value="'.$rowCellVal.'" /></td>'."\n";
}elseif( isset($_POST['possibilities']) ){
echo '<td style="'.$strStyle.'"><input class="cell" type="text" name="sudoku['.$row.']['.$column.']" size="2" value="'.implode(',',$rowCellVal).'," /></</td>'."\n";
}else{
echo '<td style="'.$strStyle.'"><input class="cell" type="text" name="sudoku['.$row.']['.$column.']" size="2" /></</td>'."\n";
}
}
echo '</tr>'."\n";
}
echo '</table>Mogelijkheden tonen: <input type="checkbox" name="possibilities" />
<br/>
<input type="submit" style="width:150px;" /></form>'."\n";
echo '<input type="button" onclick="window.location=\'./SudokuSolver.php\'" value="Legen" />';
}else{
echo '<form action="?" method="get">Oplossen? <input type="checkbox" name="solve" value="true" checked/> (Wanneer niet geklikt, wordt er slechts een link gegenereerd)<br /><table>'."\n";
for($row=0; $row<9; $row++){
echo '<tr>'."\n";
for($column=0; $column<9; $column++){
$strStyle = '';
if(($column+1)%3 == 0){
$strStyle .= 'border-right:2px solid #000000; ';
}
if(($row+1)%3 == 0){
$strStyle .= 'border-bottom:2px solid #000000; ';
}
$strValue = '';
if(isset($_GET['sudoku'][$row][$column]) && !empty($_GET['sudoku'][$row][$column])){
$strValue = 'value="'.$_GET['sudoku'][$row][$column].'" ';
}
echo '<td style="'.$strStyle.'"><input class="cell" type="text" name="sudoku['.$row.']['.$column.']" size="2" '.$strValue.' /></td>'."\n";
}
echo '</tr>';
}
echo '</table><input type="submit" style="width:150px;" /></form>'."\n";
}
?>
</body>
</html>
[/code]
[b]De class:[/b]
[code]
<?
class Sudoku{
var $_arrSudoku = array();
var $_arrTrySudokus = array();
var $_iDifficulty = 0;
function Sudoku(){
for($row=0; $row<9; $row++){
$this->_arrSudoku [$row] = array();
for($column=0; $column<9; $column++){
$this->_arrSudoku[$row][$column] = array(1=>true,2=>true,3=>true,4=>true,5=>true,6=>true,7=>true,8=>true,9=>true);
}
}
}
function Solve(){
$rowCurrentKnown = $this->GetDefined();
if($this->IsValid()){
$iCount = 0;
do{
// Try to solve it the easy way
do{
$rowOldKnown = $rowCurrentKnown;
$this->SolveByRow();
$this->SolveBycolumn();
$this->SolveByGroup();
$this->SolveByRow();
$this->SolveBycolumn();
$rowCurrentKnown = $this->GetDefined();
$this->_iDifficulty++;
}while($rowCurrentKnown != $rowOldKnown);
$iCount++;
}while(!$this->IsSolved() && $iCount < 10);
return true;
}else{
return false;
}
}
function SetValue($row, $column, $value){
if($value >0 && $value <10){
$this->_arrSudoku[$row][$column] = $value;
}
}
function GetValue($row, $column){
if( !is_array($this->_arrSudoku[$row][$column]) ){
return $this->_arrSudoku[$row][$column];
}else{
$arrReturn = array();
foreach($this->_arrSudoku[$row][$column] as $key=>$val){
if($val === true){
$arrReturn[] = $key;
}
}
return $arrReturn;
}
}
function GetAllValues(){
return $this->_arrSudoku;
}
function GetDifficulty(){
return $this->_iDifficulty;
}
function IsValid(){
$blnReturn = true;
// validate every row
for($row=0; $row<9; $row++){
$arrValues = array();
for($column=0; $column<9; $column++){
if(!is_array($this->_arrSudoku[ $row ][ $column ])){
$arrValues[] = $this->_arrSudoku[ $row ][ $column ];
}
}
// Validate the row
$iOriginalCount = count($arrValues);
$arrValues = array_unique($arrValues);
if($iOriginalCount != count($arrValues)){
$blnReturn = false;
break;
}
}
// Validate by column
if($blnReturn == true){
// validate every row
for($column=0; $column<9; $column++){
$arrValues = array();
for($row=0; $row<9; $row++){
if(!is_array($this->_arrSudoku[ $row ][ $column ])){
$arrValues[] = $this->_arrSudoku[ $row ][ $column ];
}
}
// Validate the row
$iOriginalCount = count($arrValues);
$arrValues = array_unique($arrValues);
if($iOriginalCount != count($arrValues)){
$blnReturn = false;
break;
}
}
}
if($blnReturn == true){
// Walk through the groups, using k, numberd from 1 to 9
// (left->right, top->bottom)
$arrTopoffset = array(0, 0, 0, 3,3,3, 6,6,6);
$arrLeftoffset = array(0,3,6, 0,3,6, 0,3,6);
for($k=0; $k<9; $k++){
$arrValues = array();
for($row=0; $row<3; $row++){
for($column=0; $column<3; $column++){
$y = $row+$arrTopoffset[$k];
$x = $column+$arrLeftoffset[$k];
if(!is_array($this->_arrSudoku[$x][$y])){
$arrValues[] = $this->_arrSudoku[$x][$y];
}
}
}
// Validate the row
$iOriginalCount = count($arrValues);
$arrValues = array_unique($arrValues);
if($iOriginalCount != count($arrValues)){
$blnReturn = false;
break;
}
}
}
return $blnReturn;
}
function IsSolved(){
if($this->GetDefined() == 81 && $this->IsValid()){
return true;
}else{
return false;
}
}
function GetDefined(){
$rowCount = 0;
for($row=0; $row<9; $row++){
for($column=0; $column<9; $column++){
if(!is_array($this->_arrSudoku[ $row ][ $column ])){
$rowCount++;
}
}
}
return $rowCount;
}
private function ConvertOneValueCells(){
for($row=0; $row<9; $row++){
for($column=0; $column<9; $column++){
if(is_array($this->_arrSudoku[$row][$column])){
$rowValidOptionCount = 0;
$rowLastValidOption = null;
foreach($this->_arrSudoku[$row][$column] as $key=>$value){
if($value){
$rowValidOptionCount++;
$rowLastValidOption = $key;
}
}
if($rowValidOptionCount == 1){
$this->_arrSudoku[$row][$column] = $rowLastValidOption;
}
}
}
}
}
private function SolveByRow(){
for($row=0; $row<9; $row++){
$arrDefined = array();
for($column=0; $column<9; $column++){
if(!is_array($this->_arrSudoku[$row][$column])){
$arrDefined[] = $this->_arrSudoku[$row][$column];
}
}
foreach($arrDefined as $value){
for($column=0; $column<9; $column++){
if(is_array($this->_arrSudoku[$row][$column])){
$this->_arrSudoku[$row][$column][$value] = false;
}
}
}
for($value=1; $value<=9; $value++){
$rowPossiblePositions = 0;
$arrLastCell = array();
if( !in_array($value, $arrDefined) ){
for($column=0; $column<9; $column++){
if( isset( $this->_arrSudoku[$row][$column][$value] ) && $this->_arrSudoku[$row][$column][$value] === true){
$rowPossiblePositions++;
$arrLastCell = array($row, $column);
}
}
if($rowPossiblePositions == 1){
$this->_arrSudoku[ $arrLastCell[0] ][ $arrLastCell[1] ] = $value;
}
}
}
}
$this->ConvertOneValueCells();
}
private function SolveBycolumn(){
for($column=0; $column<9; $column++){
$arrDefined = array();
for($row=0; $row<9; $row++){
if(!is_array($this->_arrSudoku[$row][$column])){
$arrDefined[] = $this->_arrSudoku[$row][$column];
}
}
foreach($arrDefined as $value){
for($row=0; $row<9; $row++){
if(is_array($this->_arrSudoku[$row][$column])){
$this->_arrSudoku[ $row ][ $column ][ $value ] = false;
}
}
}
for($value=1; $value<=9; $value++){
$rowPossiblePositions = 0;
$arrLastCell = array();
if( !in_array($value, $arrDefined) ){
for($row=0; $row<9; $row++){
if( isset( $this->_arrSudoku[$row][$column][$value] )
&& $this->_arrSudoku[ $row ][ $column ][ $value ] === true
){
$rowPossiblePositions++;
$arrLastCell = array($row, $column);
}
}
if($rowPossiblePositions == 1){
$this->_arrSudoku[ $arrLastCell[0] ][ $arrLastCell[1] ] = $value;
}
}
}
}
$this->ConvertOneValueCells();
}
private function SolveByGroup(){
// Walk through the groups, using k, numberd from 1 to 9
// (left->right, top->bottom)
$arrTopoffset = array(0, 0, 0, 3,3,3, 6,6,6);
$arrLeftoffset = array(0,3,6, 0,3,6, 0,3,6);
for($k=0; $k<9; $k++){
$arrDefined = array();
for($row=0; $row<3; $row++){
for($column=0; $column<3; $column++){
$y = $row+$arrTopoffset[$k];
$x = $column+$arrLeftoffset[$k];
if(!is_array($this->_arrSudoku[$x][$y])){
$arrDefined[] = $this->_arrSudoku[$x][$y];
}
}
}
foreach($arrDefined as $value){
for($row=0; $row<3; $row++){
for($column=0; $column<3; $column++){
$y = $row+$arrTopoffset[$k];
$x = $column+$arrLeftoffset[$k];
if(is_array($this->_arrSudoku[$x][$y])){
$this->_arrSudoku[$x][$y][$value] = false;
}
}
}
}
for($value=1; $value<=9; $value++){
$rowPossiblePositions = 0;
$arrLastCell = array();
if( !in_array($value, $arrDefined) ){
for($row=0; $row<3; $row++){
for($column=0; $column<3; $column++){
$y = $row+$arrTopoffset[$k];
$x = $column+$arrLeftoffset[$k];
if( isset( $this->_arrSudoku[$x][$y][$value] ) && $this->_arrSudoku[$x][$y][$value] === true){
$rowPossiblePositions++;
$arrLastCell = array($x, $y);
}
}
}
if($rowPossiblePositions == 1){
$this->_arrSudoku[ $arrLastCell[0] ][ $arrLastCell[1] ] = $value;
}
}
}
}
$this->ConvertOneValueCells();
}
}
?>
[\code]
Reacties
0