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…

Want to learn more? Learn by example!

Get the full commented source code of an actual commercial cross platform HTML5 game!!

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 *