BSL Dictionary - Search and compare thousands of words and phrases in British Sign Language (BSL). The largest collection of sign videos online.

Anders Giversen Sudoku Solver

This is Anders Giversen Sudoku Puzzle Solver that is another PHP solution similiar to my version.

 123456789
a
b
c
d
e
f
g
h
i
 Step by step
 

Below is the source code for Anders Giversen's Puzzle Solver.

			


<?php
  
/*
   * ------------------------------------------------------------------------------
   * "THE BEER-WARE LICENSE" (Revision 42):
   * <giversen@giver.dk> wrote this file. As long as you retain this notice you
   * can do whatever you want with this stuff. If we meet some day, and you think
   * this stuff is worth it, you can buy me a beer in return. Anders Giversen
   * ------------------------------------------------------------------------------
   */
  
 
  // ---- F U N C T I O N S ----
  
  // Show grid.
  
function showGrid($grid$inputForm$small$missing) {
    global 
$rowName$missingSquareCells;
    
    if (
$inputForm) {
      
printf("<form class=\"sudoku-form\" action=\"%s\" method=\"post\">\n"$_SERVER['PHP_SELF']);
      print(
"<table border=\"0\" cellspacing=\"1\" cellpadding=\"1\">\n");
      
      print(
"<tr><td>&nbsp;</td>");
      for (
$i 1$i <= 9$i++) {
        
printf("<td style=\"text-align: center;\">%s</td>"$i);
      }
      print(
"</tr>\n");
    } else {
      print(
"<table border=\"1\" cellspacing=\"0\" cellpadding=\"0\">\n");
    }
    
    for (
$i 0$i 9$i++) {
      
printf("<tr>%s", ($inputForm) ? "<td>$rowName[$i]</td>" "");
      
      for (
$j 0$j 9$j++) {
        
// Determine the background color based on the current square cell.
        
if ( (($i || $i 5) && ($j && $j 6)) || (($i && $i 6) && ($j || $j 5)) ) {
          
$style "background-color: #EEEEEE;";
        } else {
          
$style "background-color: #ffffff;";
        }
        
        if (
$inputForm) {
          
printf("<td><input name=\"%s\" style=\"%s\" type=\"text\" size=\"1\" maxlength=\"1\" value=\"%s\"/></td>"
                
$rowName[$i] . ($j+1), $style$grid[$i][$j]);
        } else {
          
printf("<td style=\"%s%s text-align: center; padding: 4px;\">%s</td>"$style, ($small) ? " width: 1.5em;" " width: 6em;"
                
, empty($grid[$i][$j]) ? "&nbsp;" $grid[$i][$j]);
        }
      }
      
      print(
"</tr>\n");
    }
    
    if (
$inputForm) {
      print(
"<tr><td>&nbsp;</td><td><input type=\"checkbox\" name=\"step-by-step\" /></td><td colspan=\"8\">Step by step</td></tr>\n");
      print(
"<tr><td>&nbsp;</td><td colspan=\"9\" style=\"text-align: center;\"><input type=\"submit\" name=\"submit\" value=\"Solve\" />"
           
."</td></tr>\n");
      print(
"</table>\n</form>\n\n");
      print(
"<script type=\"text/javascript\">\n<!--\ndocument.forms[0].a1.focus();\n-->\n</script>\n");
    } else {
      print(
"</table>\n");
      
      if (
$missing) {
        
printf("<div class=\"missing\">Missing square cells: %s</div>\n\n"$missingSquareCells);
      }
    }
  } 
// showGrid
  
  
  // Get the possible values based on the supplied row and column.
  
function getPossibleValues($grid$row$column, &$changed) {
    global 
$missingSquareCells;
    
    
$count[0] = array(000000000);
    
$count[1] = array(000000000);
    
$used = array();
    
$possibleValues "";
    
    
// Find used values in the supplied row and column.
    
for ($i 0$i 9$i++) {
      
$entry = array($grid[$i][$column], $grid[$row][$i]);
      
      for (
$j 0$j 2$j++) {
        if (!empty(
$entry[$j])) {
          
$possibilities $entry[$j];
        } else {
          
$possibilities "123456789";
        }
        
        
$length strlen($possibilities);
        for (
$c 0$c $length$c++) {
          if ((
$length == 1) && !in_array($possibilities[$c], $used)) {
            
$used[] = $possibilities[$c];
          }
          
          
$count[$j][($possibilities[$c] - 1)]++;
        }
      }
    }
    
    
// Determine the possible values.
    
if (!empty($grid[$row][$column])) {
      
$possibilities $grid[$row][$column];
    } else {
      
$possibilities "123456789";
    }
    
    
// Eliminate used values.
    
$length strlen($possibilities);
    for (
$c 0$c $length$c++) {
      if (!
in_array($possibilities[$c], $used)) {
        
$possibleValues .= $possibilities[$c];
      }
    }
    
    
// Check uniqueness.
    
$length strlen($possibleValues);
    for (
$c 0$c $length$c++) {
      if ((
$count[0][($possibleValues[$c] - 1)] == 1) || ($count[1][($possibleValues[$c] - 1)] == 1)) {
        
$possibleValues $possibleValues[$c];
        break;
      }
    }
    
    
// Has the possible values been updated?
    
if (!$changed && ($grid[$row][$column] != $possibleValues)) {
      
$changed 1;
    }
    
    
// Update count of missing square cells if a unique solution has been found.
    
if (strlen($possibleValues) == 1) { $missingSquareCells--; }
    
    
// Return '-' if imposible otherwise return the possible values.
    
if (strlen($possibleValues) == 0) {
      return 
'-';
    } else {
      return 
$possibleValues;
    }
  } 
// getPossibleValues
  
  
  // Update each square cell in the supplied 3x3 square based on the value of the other cells
  
function updateSquareCells(&$grid$square, &$changed) {
    global 
$missingSquareCells;
    
    
$count = array(000000000);
    
$used = array();
    
    
// Find used values in the supplied 3x3 square.
    
for ($i 0$i 9$i++) {
      if (!empty(
$grid$square[$i][0] ][ $square[$i][1] ])) {
        
$possibilities $grid$square[$i][0] ][ $square[$i][1] ];
      } else {
        
$possibilities "123456789";
      }
      
      
$cell[$i][0] = $square[$i];
      
$cell[$i][1] = $possibilities;
      
      
$length strlen($possibilities);
      for (
$c 0$c $length$c++) {
        if ((
$length == 1) && !in_array($possibilities[$c], $used)) {
          
$used[] = $possibilities[$c];
        }
        
        
$count[($possibilities[$c] - 1)]++;
      }
    }
    
    
// Update square cells.
    
for ($i 0$i 9$i++) {
      
$length strlen($cell[$i][1]);
      
      if (
$length 1) {
        
$possibleValues "";
        
        
// Eliminate used values.
        
for ($c 0$c $length$c++) {
          if (!
in_array($cell[$i][1][$c] , $used)) {
            
$possibleValues .= $cell[$i][1][$c];
          }
        }
        
        
// Check uniqueness.
        
$length strlen($possibleValues);
        for (
$c 0$c $length$c++) {
          if (
$count[($possibleValues[$c] - 1)] == 1) {
            
$possibleValues $possibleValues[$c];
            break;
          }
        }
        
        
// Has the possible values been updated?
        
if (!$changed && ($grid$cell[$i][0][0] ][ $cell[$i][0][1] ] != $possibleValues)) {
          
$changed 1;
        }
        
        
// Update count of missing square cells if a unique solution has been found.
        
if (strlen($possibleValues) == 1) { $missingSquareCells--; }
        
        
// Update square cell with possible values or '-' (and break the loop) if imposible.
        
if (strlen($possibleValues != 0)) {
          
$grid$cell[$i][0][0] ][ $cell[$i][0][1] ] = $possibleValues;
        } else {
          
$grid$cell[$i][0][0] ][ $cell[$i][0][1] ] = '-';
          
          return 
0;
        }
      }
    }
    
    return 
1;
  } 
// updateSquareCells
 
  // Update grid based on rows, columns and 3x3 squares
  
function updateGrid(&$grid$square$stepwise) {
    global 
$missingSquareCells;
    
    
$initialLoop 1;
    
$updated 1;
    
    while (
$updated) {
      
$updated 0;

      
// Update square cells based on rows and columns
      
for ($i 0$i 9$i++) {
        for (
$j 0$j 9$j++) {
          if (empty(
$grid[$i][$j]) || (strlen($grid[$i][$j]) > 1)) {
            
$grid[$i][$j] = getPossibleValues($grid$i$j$updated);
            
            if (
$grid[$i][$j] == '-') {
              return 
0;
            }
          }
        }
      }
      
      
// Update square cells based on 3x3 squares.
      
if ($initialLoop || $updated) {
        for (
$i 0$i 9$i++) {
          if (!
updateSquareCells($grid$square[$i], $updated)) {
            return 
0;
          }
        }
      }

      
// Break the loop if a solution has been found.
      
if ($missingSquareCells == 0) {
        
$updated 0;
      } elseif (
$stepwise) {
        
showGrid($grid001);
      }
      
      if (
$initialLoop) { $initialLoop 0; }
    }
    
    return 
1;
  } 
// updateGrid

  // Initialize data.
  
$showInputForm 1;
  
$missingSquareCells 0;
  
$rowName = array('a''b''c''d''e''f''g''h''i');

  for (
$i 0$i 9$i++) {
    for (
$j 0$j 9$j++) {
      
$grid[$i][$j] = '';
    }
  }
 
  
// Solve Sudoku puzzles.
  
if (isset($_POST['submit']) && ($_POST['submit'] == "Solve")) {
    
$showInputForm 0;
    
$failed 0;
    
$error "";
  
    
// Input validation.
    
if (isset($_POST['step-by-step'])) {
      
$stepwise 1;
    } else {
      
$stepwise 0;
    }
    
    
$i 0;
    foreach (
$rowName as $row) {
      for (
$j 1$j <= 9$j++) {
        
$entry trim($_POST["$row$j"]);
    
        if (!empty(
$entry)) {
          if (!
preg_match("/^[0-9]$/"$entry)) {
            
$error .= sprintf("%s%s", empty($error) ? "" ", ""$row$j");
            
$showInputForm 1;
          }
          
          
$grid[$i][($j-1)] = $entry;
        } else {
          
$missingSquareCells++;
        }
      }
      
      
$i++;
    }
  
    if (!
$showInputForm) { // Valid input.
      
print("<h2>Sudoko puzzle</h2>\n");
      
showGrid($grid010);
      
printf("Missing square cells: %s\n"$missingSquareCells);
      
      
// Define 3x3 squares - $square[0] to $square[8].
      
$row 0;
      
$m 0;
      
      for (
$i 0$i 3$i++) {
        
$column 0;
        
        for (
$j 0$j 3$j++) {
          for (
$k $row$k < ($row 3); $k++) {
            for (
$l $column$l < ($column 3); $l++) {
              
$square[$m][] = "$k$l";
            }
          }
          
          
$column += 3;
          
$m++;
        }
        
        
$row += 3;
      }
      
      
printf("\n%s\n", ($stepwise) ? "<h2>Step by step</h2>" "<h2>Solution</h2>");
      
      
// Step 1 - determine the possible values for each square cell based on row, column and 3x3 square.
      
if ($stepwise) {
        print(
"<h3>Step 1: Determine the possible values for each square cell</h3>\n");
        print(
"<div class=\"note\">This is done based on the row and column of each square cell along with the 3x3 square"
             
." containing the cell in question. Each row, column and 3x3 square must contain the numbers 1 through 9.</div>\n");
      }
      
      if (!
updateGrid($grid$square$stepwise)) {
        print(
"<div class=\"error\">This puzzle may be unsoveable! Cells containing '-' indicates a conflict.</div>\n");
        
$failed 1;
      }

      
showGrid($grid0, !$failed0);
      
printf("Missing square cells: %s\n"$missingSquareCells);
    } else { 
// Invalid input.
      
printf("<div class=\"error\">Invalid Sudoku (%s)!</div>\n"$error);
    }
  }
  
  
// Show input form.
  
if ($showInputForm) {
    
showGrid($grid100);
  }
?>

1 Comments

Hi there. I've enjoyed Sudoku for quite a few years. Currently I use the 16X16 monster Sudoku puzzle sheets. There are many to play online, or download to play on the I pad or I phone. I like to print them off and take them where ever. Waiting for the bus, or waiting anywhere. It was another site which sent me here. I'm curious about how these puzzles are generated, thinking that I might be able to understand enough to modify this code to generate the 16X16 sudoku for personal use.

Any thoughts would be appreciated,

David Hubbard

Canadian Sudoku Fan
Comment 1 by David Hubbard. Made on the 01st Dec 2012.

Leave a Comment on this Page

Sorry, Commenting is now disabled