1 Sudoku Solver in JavaScript {anchor:Soduko Solver in JavaScript} One good thing about the holidays is that they usually give me the opportunity to spend some quality time with my computer. I've taken advantage of this to finish off a {link:Sudoku|http://en.wikipedia.org/wiki/Sudoku} solver written in JavaScript. This is the smallest solver that I've seen. Notice that the method to solve the puzzle is only slightly larger than the method to display it. {code} // Author: Kevin Greer, Date: Dec 25, 2005 -- Copyright 2005, All Rights Reserved s = [[[[0,0,0],[0,7,1],[0,0,5]], [[5,0,0],[0,6,9],[0,7,1]], [[0,7,1],[8,5,3],[4,2,0]]], [[[0,1,0],[0,0,2],[0,0,0]], [[7,8,0],[1,5,4],[0,9,2]], [[0,4,0],[3,6,0],[1,8,0]]], [[[0,6,4],[0,2,3],[0,5,0]], [[9,0,5],[0,1,0],[0,0,0]], [[7,0,0],[5,9,0],[0,0,0]]]] function display() { for ( a = 0 ; a < 3 ; a++ ) { for ( b = 0 ; b < 3 ; b++ ) { for ( c = 0 ; c < 3 ; c++ ) { for ( d = 0 ; d < 3 ; d++ ) document.write(" " + s[a][c][b][d]) if ( c < 2 ) document.write(" |") } document.write("<br/>") } if ( a < 2 ) document.write("-------+-------+-------<br/>") } } function solve(a, b, c, d) { if ( d == 3 ) return solve(a, b, c+1, 0) if ( c == 3 ) return solve(a, b+1, 0, 0) if ( b == 3 ) return solve(a+1, 0, 0, 0) if ( a == 3 ) return true if ( s[a][b][c][d] != 0 ) return solve(a, b, c, d+1) outer: for ( var j = 1 ; j <= 9 ; j++ ) { for ( var x = 0 ; x < 3 ; x++ ) for ( var y = 0 ; y < 3 ; y++ ) if ( s[a][b][x][y] == j || s[a][x][c][y] == j || s[x][b][y][d] == j ) continue outer s[a][b][c][d] = j if ( solve(a, b, c, d+1) ) return true s[a][b][c][d] = 0 } return false } display() document.write("<br/>solving...<br/><br/>") if ( solve(0,0,0,0) ) display() {code} The solver outputs the puzzle, followed by its solution: {image:output.gif} You can find some solvers written in other languages linked from {link:lambda-the-ultimate|http://lambda-the-ultimate.org/node/view/772}. 2006-01-01 18:23:14.586 2005-12-25 14:34:35.345 Nice one. Happy New Year !!! 2005-12-29 13:40:37.035 2005-12-29 13:40:36.96 Kevin, really good brute force solver, you've made! Are you sure return solve(a, b, c+1, 0) if d==3 return solve(a, b+1, 0, d) if c==3 return solve(a+1, 0, c, d) if b==3 shouldn't be return solve(a, b, c+1, 0) if d==3 return solve(a, b+1, 0, 0) if c==3 return solve(a+1, 0, 0, 0) if b==3 ? (I rewrote it in Ruby) regards Christer 2005-12-29 21:06:45.618 2005-12-29 21:06:45.551 Christer, Good point. The two versions are equivalent but yours avoids the variable lookups for values that we already know are zero anyway. Thanks 2005-12-30 22:34:37.926 2005-12-30 22:34:37.846 Here's a link to Christer's {link:Ruby Port|http://www.ruby-forum.com/topic/50188}. 2006-01-20 15:42:25.71 2006-01-20 15:00:18.498 Here's a list of solvers in other languages: * {link:J|http://www.vector.org.uk/archive/v214/sudoku.htm} * {link:Scheme|http://schemely.blogspot.com/2006/02/scheme-sudoku-solver.html} * {link:Lisp|http://www.jalat.com/blogs/lisp?id=4} * {link:APL|http://www.vector.org.uk/archive/v214/sudoku2.htm} * K: {link:#1|http://www.nsl.com/k/sudoku/rh.k} {link:#2|http://www.nsl.com/k/sudoku/aw.k} * {link:SQL!!!|http://www.vsj.co.uk/articles/display.asp?id=540} * {link:Python|http://www.norvig.com/sudoku.html} * {link:Smalltalk|http://blog.laubach.at/smalltalk/blogView?showComments=true&entry=3347782296} * {link:Factor|http://factor-language.blogspot.com/2007/02/sudoko-solver-in-factor.html} 2007-02-26 09:18:19.37 2006-01-30 13:19:03.11 More short solutions: {link:Java|http://blogs.asman-it.com.au/dasman/index.php/20060724/java-sudoku-solver-in-6-lines}, {link:Perl|http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html}, {link:Ruby + Others|http://markbyers.com/moinmoin/moin.cgi/ShortestSudokuSolver} 2006-07-26 10:11:09.875 2006-07-26 10:11:09.782 Mon Dec 26 19:53:24 EST 2005