Sudoku in JavaScript

This is a Sudoku puzzle generator and solver. This program provides two generation algorithms, a solver and methods to update and check the state of the puzzle. I had found a JavaScript Sudoku at http://www.dhtmlgoodies.com/scripts/game_sudoku/game_sudoku.html which I thought was pretty cool, however, it didn’t create very good puzzles. Most had more than one solution and if you didn’t find the solution it chose as a the final solution, you would never finish the game. I started thinking about how you would actually create a working Sudoku puzzle. This is my first attempt.

The puzzle is generated using the solver to solve an empty Sudoku board. It implements a backtracking algorithm in which it randomly selects numbers to try in each cell. It starts with the first cell and picks a random number. If the number works in the cell, it recursively chooses the next cell and starts again. If all the numbers for a cell have been tried and none work, a number chosen for a previous cell cannot be part of the solution so we have to back up to the last cell and choose another number. If all the numbers for that cell have also been tried, we back up again. This continues until a value is chosen for all 81 cells. (The actual implementation is pretty much what is described here though it does use some optimizations and tricks so it isn’t too painfully slow. If you’re interested check out the source which is heavily commented.)

Once the board is filled in, values are removed until no more values can be removed without creating a puzzle with more than one solution.  Actually, Medium and Hard are guaranteed to have only a single solution. Easy uses a naive algorithm similar to that used at the dhtmlgoodies.com link above which may have more than one solution. Don’t worry though, if you find a valid solution the game will finish.

The game can be found here. The source contains very detailed comments describing how the algorithm works. The source can be viewed here.

Have fun. Send any comments, bugs, contributions to djrager@fourthwoods.com

Useful resources:

Category(s): Algorithms, JavaScript, Programming
Tags: , ,

14 Responses to Sudoku in JavaScript

  1. Thnaks

    I just want to try!

    Dinos

  2. Hi,

    We visited your website and interested with your sudoku javascript game.

    We have a project and I would like to talk about it a bit.

    We want to build a sudoku server and it ll have members and members ll play the game synchronously.
    And the winner of players ll be annnounced on other player’s screen and it ll start new game for everybody. it ll have limited time period to play a single game and it ll have limited times to play sudoku daily. Plus we ll have score board and all things, simply.

    We would like to ask you about the price for the full project, described above.
    Alternatively if you are unable to do it, we would like to know the price for your sudoku on your website.

    We ll be looking forward to hear from you.
    Regards,


    Ömer Eral
    Web-Yazılım
    Burhaniye Mah. Doğu Karadeniz Cad. Selvili Evler No:26 / E (Villa 5)
    Beylerbeyi / Üsküdar / İSTANBUL
    Tel : +90 (216) 557 72 72 – Dahili: 155
    Fax : +90 (216) 422 22 90
    E-mail : oeral@beyaz.net
    Web : http://www.beyaz.net

    • Hi Ömer,

      That sounds like an interesting project. Unfortunately I’m not able to take on that project at this time.

      You are however free to use my code from the website if you wish. It is open source under a BSD style license so you can use it pretty much how you wish and I don’t require any payment. The only thing I ask is that you give me an acknowledgement in your documentation as described in the source header block.

      The source for the generator/solver can be downloaded here:
      http://www.fourthwoods.com/sudoku.js

      The source for the UI components are in the html:
      http://www.fourthwoods.com/sudoku.html

      Feel free to contact me with any questions about the code. I’ll try to help the best I can.

      I’ll follow up with an email to you in case you are not watching this post.

  3. Hi!
    Nice job!!! Can this script be adapted for Adobe InDesign?

    Thanks!

    • I’m not familiar with InDesign but it shouldn’t be too hard to adapt. The generator/solver probably won’t need many changes if any. The UI pieces will need to be rewritten according to how UIs are done in InDesign. Should be pretty straight forward though.

      Let me know if you have any questions with it and I’ll try to help as best I can.

  4. hai,can you help me in creating a able with ascending value every cell but half of the cell value is hidden…since i am making a elearning website and i will allow the student/s to fill up the missing number in the table….i would be greatfull with any help.

  5. Hey there. When I call newGame and then try to retrieve the matrix, it hasn’t been masked yet! Any clue as to why? This seems to be a timing issue. After a few MS the matrix is properly masked. I thought javascript was synchronous. What is going on here that causes it to not update in time. Were you doing something asynchronously? In my local copy I am going to try a callback and see if that fixes the issue.

    • Also, why do you have two copies of the newgame function?

    • JavaScript is “synchronous” in that it will block the callee until it is complete. However, this also has the undesired effect of blocking the entire browser making it unresponsive until the JavaScript is finished.

      When coding for a browser, the JavaScript should be written in such a way that it still allows the browser to function. This is done by periodically calling the setTimeout() function to temporarily return control to the browser so it can process any queued up messages. After the “timeout” has expired, the supplied JavaScript function is called to resume our processing.

      The _newGame function if I recall correctly does not do this and is obsolete. You should instead use the newGame function. Note however, that when this function returns the puzzle will probably not be completed. Instead, install a function for the done callback. When the puzzle is finished, this callback function will be called. From here you will be guaranteed the puzzle will be completed.

      See the source for sudoku.html for an example of how this is used.

  6. Hey, is this line a bug?
    for(var col = 0; col < col; k++) {

    // col will never be < col; so this code does nothing.
    // Also, nothing increments col, and nothing tests it?
    // There seems to be unreachable code inside

    • Yep it absolutely is a bug. It’s in the “shuffle” method which isn’t used for the board generation in the actual game. I just included it as an illustration of an alternative board generation algorithm. I’ll fix it next time I mess with the code. I do want to eventually update this to be more mobile friendly at some point. Not sure when that will be…

  7. Hey….great script here. I’m going to convert it to a powershell script if you don’t mind. Let me know if this will be a problem.

  8. Hi,

    I just found this script and it works well when I run it locally and also from our shared server.

    However when I try to embed it into a wordpress page it will not display the board. I think it my not be firing the init function but I don’t know enough to know if this is the problem or it is something else.

    I saved the javscript code into a js file and changed the line of code which loads that script in the html file. When I execute the html file (which is basically the same code as you use to display the game minus the google forever code) it works.

    When I take that html code and place it into a WordPress page, removing the html tags and a few of the lines following that tag at the top of the page , it does not load the board. I tried to change the body tag to a different element, since the body tag is already executed when the page is loaded, but it didn’t make a difference.

    Any suggestions are appreciated.

    thanks

Leave a Reply

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