start > 2005-12-25 > 1

2005-12-25 #1

Created by kgr. Last edited by kgr, 4 years and 245 days ago. Viewed 2,694 times. #9

[diff] [history] [edit] [rdf]

labels

attachments

output.gif (7084)

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

// Author: Kevin Greer,   Date: Dec 25, 2005  --  Copyright 2005, All Rights Reserveds = [[[[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()