### 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:

Tags: , ,

Saturday, February 5th, 2011

#### 15 Comments to Sudoku in JavaScript

• dinos says:

Thnaks

I just want to try!

Dinos

• omer says:

Hi,

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

• David says:

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.

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.

• Jerome says:

Hi!

Thanks!

• David says:

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.

• 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.

• Forrest says:

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.

• Forrest says:

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

• Forrest says:

Hmm, so using the _newGame function instead of newGame fixed the issue. I’m not sure why.

• David says:

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.

• Kirk says:

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

• David says:

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…

• Robert says:

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.

• Ron says:

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

• Ron says:

I can get it working in WordPress using the Iframe plugin but would prefer to insert it directly into a WP page if possible.