Sudoku creator/solver with PHP

Emanuele Feronato Game design, Php

This is an old project for a class held in 2005.

At that time, Sodoku game was very popular in Italy, and I saw quite a lot of Flash games based upon it.

If you don’t know what is a Sudoku, Wikipedia says is a logic-based number-placement puzzle. The objective is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes (also called blocks or regions) contains the digits from 1 to 9 only one time each. The puzzle setter provides a partially completed grid.

The script consists in a set of functions that emulate the “human way” to solve a Sudoku game, with trials and errors, using backtracking.

The only thing you need to know is how I represent the Sudoku table inside the script.

It’s an array (line 193) with 81 values representing positions from 0 to 80. The value at n-th position is the one you will find on the table at row floor(n/9) and column n%9.

A value from 1 to 9 represents a know number of a Sudoku table, while a zero represents an unknown one.

For this reason, an array filled only with zeros like the one in the script will generate a new, full Sudoku.

This is the script:

And this is an example of a new sudoku generated with the script:

Refresh the iframe to create another one.

This script too is quite easy to port in AS3, if you convert it I’ll post it on the blog.

I should have an old AS2 conversion too somewhere in my hard disks…

Comments 36

  1. Pingback: Creare un risolutore di sudoku con php : sastgroup.com

  2. Pingback: Risolvere sudoku con php | Web2Eg

  3. Kevin Hoyt

    I got most of the way through an AS3 port, but got hung up on the data type of “next_move” in the solve() method. What’s that supposed to be?

    The scan_sudoku_for_unique seems to either return a boolean, or an array. Yet the next line in the solve() method checks it for a boolean. The line after that attempts to pop a value off what is initially an empty array and return that value into next_move. The subsequent “if” appears to treat next_move as an array.

    I’m not a PHP pro, so I’m likely missing something here, but if you could shed a little light on the data type/expectations for next_move, I’d really appreciate it.

    Thanks,
    Kevin

  4. Pingback: Creare un risolutore di sudoku con php

  5. Post
    Author
    Emanuele Feronato

    next_move determines if I can make another “move” (placing another number or not).

    If I can’t place a number, I have to backtrack the sudoku

  6. Pingback: A strange way AS3 manages arrays : Emanuele Feronato

  7. Pingback: Sudoku creator/solver with AS3 : Emanuele Feronato

  8. Richard Howarth

    Thanks for this simple and easy to understand technique.

    It ported fairly easily to the KiXtart scripting language with a few changes where the interpreter does not have the wealth of built-ins of PHP.

    I’ve posted the ported script (with some additional code to create the starting grid) in the KiXtart community board here: http://www.kixtart.org/forums/ubbthreads.php?ubb=showflat&Number=191555

    It’s a bit slow in KiXtart (it takes about 23 seconds to complete an empty grid), but watching the guesses is quite soothing.

  9. nicolasd

    hi, i’m trying your code just for a test because i ve ceded one too, but i ve a non stop loop and nothing works, i dont know what isnt working but u call a variable x on solve method without declare it first, and i think the problem is due to that.
    if you have a correction of your code which is working can you send me by mail.
    i can also show you mine if needed

  10. Jim Nelms

    Hi All,

    I would be pleased to hear from a programmer to write the code for a new type of ‘Sudoku’ puzzle, if you are interested and prepared to sign a NDA please reply at the earlist, the successful candidate will be given shares in the company as a reward. Regards, Jim Nelms

  11. Rizta Husni Ananda

    For this particular problem (Platinum Blonde from Wikipedia):
    $sudoku = array(0,0,0,0,0,0,0,1,2,0,0,0,0,0,0,0,0,3,0,0,2,3,0,0,4,0,0,0,0,1,8,0,0,0,0,5,0,6,0,0,7,0,8,0,0,0,0,0,0,0,9,0,0,0,0,0,8,5,0,0,0,0,0,9,0,0,0,4,0,5,0,0,4,7,0,0,0,6,0,0,0);
    And its solution:
    839465712
    146782953
    752391486
    391824675
    564173829
    287659341
    628537194
    913248567
    475916238

    My PHP script ran for 6.64 secs in my system. And yours for about 3 times longer.
    But still, your way of thinking is really interesting. Very much different than mine. I myself never use array push pop diff etc.
    Besides, I already spent over 500 lines of code for the basic elimination, trial & error, backtracking function. But yours only took less than 200 LOC for everything.
    Nice and neat. Good one dude!

  12. Rizta Husni Ananda

    Argh shoot…
    Sorry my comment ruin your page. I didn’t know that it would be displayed like that. You can just delete it if you mind.
    Btw, on line 157 there’s a bit warning. Some kind of undefined variable. Thank you.

  13. David

    Three bugs:

    The initial array is busted, it is too short.

    FIX:

    $sudoku = array(
    0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0,
    0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0,
    0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0
    );

    In the function “solve”, initialize $x before the loop:

    $x = 0;

    while (!is_solved_sudoku($sudoku)) {
    $x++;

    And the big one, check if a key for the array is valid, before trying to access it:

    function next_random($possible)
    {
    $max = 9;

    for ($x = 0; $x <= 80; $x++) {
    $keyExists = array_key_exists($x, $possible);

    if ($keyExists) {
    if ( (count($possible[$x]) 0) ) {
    $max = count($possible[$x]);
    $min_choices = $x;
    }
    }
    }

    return $min_choices;
    }

    Very nice code, works extremely fast.

  14. David

    Three bugs to fix.

    1) The initial array is busted, it is too short.

    FIX:

    $sudoku = array(
    0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0,
    0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0,
    0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0
    );

    2) Initialize the variable $x before the loop within the function “solve”.

    $x = 0;

    while (!is_solved_sudoku($sudoku)) {
    $x++;

    3) Check if the array has the key available.

    function next_random($possible)
    {
    $max = 9;

    for ($x = 0; $x <= 80; $x++) {
    $keyExists = array_key_exists($x, $possible);

    if ($keyExists) {
    if ( (count($possible[$x]) 0) ) {
    $max = count($possible[$x]);
    $min_choices = $x;
    }
    }
    }

    return $min_choices;
    }

  15. Post
    Author
  16. jay patil

    I wanna display a grid of numbers from 1-8..
    I want each number to be unique in its row as well as in its column..
    Can u help me based on ur sodoku algo…

  17. debutante

    it’s work fine if :
    1) Add two @ near count($possible in function “next_random”

    function next_random($possible)
    { $max = 9;
    for($x=0;$x<=80;$x++)
    { if ((@count($possible[$x])0))
    {

    2) Initialize the variable $x before the loop in the function “solve”

    function solve($sudoku)
    { $x=0;
    $start = microtime();
    $saved = array();
    $saved_sud = array();
    while(!is_solved_sudoku($sudoku))
    { $x+=1;

    it’s nicer if you add in “print_sudoku” some colors

    function print_sudoku($sudoku)
    { $color = array(‘pink’,’gold’);
    $html = “”;
    for($x=0;$x<=8;$x++)
    { $html .= "”;
    for($y=0;$y<=8;$y++)
    { $bgcol = floor($y/3)%2;
    $bgcol = floor($x/3)%2 ? !$bgcol : $bgcol ;
    $html.= "”.$sudoku[$x*9+$y].””;
    }
    $html .= “”;
    }
    $html .= “”;
    return $html;
    }

  18. Pingback: sudoku formula explanation - DL-UAT

  19. Pingback: finding formula from table | Question and Answer

Leave a Reply

Your email address will not be published. Required fields are marked *