randomfox (randomfox) wrote,
randomfox
randomfox

Sudoku Solver in Python for Google App Engine

This Sudoku Solver is written for Google App Engine. It requires jQuery for AJAX but everything else it needs is provided by App Engine.


app.yaml:

application: sudokusolver
version: 1
runtime: python
api_version: 1

handlers:
- url: /js
  static_dir: js

- url: /.*
  script: sudoku.py

# vim:ft=text:


sudtempl.htm:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
    "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">

<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" />
<meta http-equiv="Content-Language" content="en-us" />
<meta http-equiv="imagetoolbar" content="false" />
<meta name="MSSmartTagsPreventParsing" content="true" />
<meta name="author" content="Po Shan Cheah" />

<title>Sudoku Solver</title>

<style type="text/css">
body {
    background: #fff none;
    color: #000;
    font: normal 14px Tahoma, Verdana, Arial, Helvetica, sans-serif;
}

.error {
    color: red;
}

#output {
    white-space: pre;
    font: normal 14px monospace;
}
</style>

<script type="text/javascript" src="/js/jquery-1.2.6.min.js"></script>
<script type="text/javascript">
    $(document).ready(function(){
	$("form#puzform").submit(function(){
	    $("#output").html("Working...");
	    $.post("/ajax",{ 
		input: $("#input").val() 
	    }, function(out) {
		$("#output").html(out);
	    });
	    return false;
	});
    }); 
</script>
</head>

<body>
    <h1>Sudoku Solver</h1>

    <form id="puzform" action="/" method="post">
	Enter the puzzle below:<br />
	<textarea name="input" id="input" rows="12" cols="30">{{ puz }}</textarea><br />
	<input type="submit" value="Solve it!" />
    </form>
    <hr />
    <div id="output">{{ output }}</div>
</body>
</html>


sudoku.py:

# Sudoku Solver for Google App Engine
# Last updated: August 13, 2008
# Author: Po Shan Cheah

import cgi
import re
import time
from google.appengine.ext import webapp
from google.appengine.ext.webapp.util import run_wsgi_app
from google.appengine.ext.webapp import template

# Replace newlines with <br> tags. Consecutive <br> tags need to be
# separated by non-breaking spaces so that the browser won't collapse the
# blank lines.
def nl2br(str):
    return re.sub('\n+', lambda mobj: '<br>' + '&nbsp;<br>' * (len(mobj.group(0)) - 1), str)

class MainPage(webapp.RequestHandler):

    default_puz = """xxx 6xx 9x2
xx6 1xx x87
2x7 5xx xx1

xxx xx8 7xx
4x2 xxx 1x6
xx9 2xx xxx

6xx xx3 5x8
59x xx1 2xx
8x4 xx7 xxx"""

    output = ''

    def write(self, msg):
	self.output += msg

    def write_error(self, msg):
	self.output += '<span class="error">Error: %s</span>\n' % msg

    def write_bold(self, msg):
	self.output += '<strong>%s</strong>\n' % msg

    def render_template(self, puz, output):
	self.response.out.write(template.render("sudtempl.htm", 
	    { 'puz' : puz, 'output' : output }))

    # This is the initial page. Just display the form and put a default
    # puzzle into the textbox.
    def get(self):
	self.render_template(self.default_puz, '')

    # Solve the puzzle in input and output the solution.
    def solve_puzzle(self, input):
	if self.process_input(input):
	    self.write_bold("Puzzle:")
	    self.print_board()
	    self.write("\n")

	    if self.check_board():
		self.nodecount = 0
		starttime = time.clock()
		if not self.try_board(0, 0):
		    self.write("No solution found\n")
		elapsedtime = time.clock() - starttime

		self.write("""
%d nodes examined.
Elapsed time: %.3f seconds.
""" % (self.nodecount, elapsedtime))

    # Non-AJAX handler so we build up the whole page with the solution inside.
    def post(self):
	input = self.request.get('input')

	self.solve_puzzle(input)

	# Leave the user's input in the textbox when displaying the form.
	self.render_template(cgi.escape(input), nl2br(self.output))

    # Parse the board info from the text area.
    def process_input(self, input):
	lineno = 0
	self.board = []

	for line in input.split('\n'):
	    line = re.sub(r'\s+', '', line)
	    if len(line) == 0:
		continue

	    lineno += 1
	    if len(line) < 9:
		self.write_error('Line %d is too short.' % lineno)
		return False

	    # Take the first 9 chars of the line and convert them to int or 0.
	    self.board.append([c.isdigit() and int(c) or 0 for c in line[:10]])

	if lineno < 9:
	    self.write_error('Not enough rows. Only %d rows found.' % lineno)
	    return False

	return True

    # Display the board.
    def print_board(self):
	for i in range(0, 9):
	    self.write('%d: %s\n' % (i + 1,
		' '.join([cell == 0 and 'x' or str(cell)
		    for cell in self.board[i]])))

    # Check board for simple inconsistencies.
    def check_board(self):

	# Check rows
	for i in range(0, 9):
	    used = [ False ] * 10
	    for j in range(0, 9):
		cell = self.board[i][j]
		if cell and used[cell]:
		    self.write_error('Digit %d occurs more than once in row %d' % (cell, i + 1))
		    return False
		else:
		    used[cell] = True

	# Check columns
	for j in range(0, 9):
	    used = [ False ] * 10
	    for i in range(0, 9):
		cell = self.board[i][j]
		if cell and used[cell]:
		    self.write_error('Digit %d occurs more than once in column %d' % (cell, j + 1))
		    return False
		else:
		    used[cell] = True

	# Check 3x3 blocks
	for ii in range(0, 9, 3):
	    for jj in range(0, 9, 3):
		used = [ False ] * 10
		for i in range(ii, ii + 3):
		    for j in range(jj, jj + 3):
			cell = self.board[i][j]
			if cell and used[cell]:
			    self.write_error('Digit %d occurs more than once in 3x3 block at %d,%d' % (cell, ii+1, jj+1))
			    return False
			else:
			    used[cell] = True

	return True

    # Return a list of numbers that could go into cell row, col on the board.
    def get_possible(self, row, col):
	used = [ False ] * 10

	# Check row and column
	for i in range(0, 9):
	    used[self.board[row][i]] = True
	    used[self.board[i][col]] = True

	# Check 3x3 block containing this cell
	brow = row - row % 3
	bcol = col - col % 3
	for i in range(brow, brow + 3):
	    for j in range(bcol, bcol + 3):
		used[self.board[i][j]] = True

	# Return numbers that have not been used in the containing row, column,
	# and block.
	return [i for i in range(1,10) if not used[i]]

    # Recursive function to find a solution by exhaustive search.
    def try_board(self, row, col):
	if row >= 9:
	    self.write_bold("Found a solution:")
	    self.print_board()
	    return True

	self.nodecount += 1

	nextrow, nextcol = row, col + 1
	if nextcol >= 9:
	    nextrow, nextcol = row + 1, 0

	# Skip over cells that are already filled.
	if self.board[row][col] != 0:
	    return self.try_board(nextrow, nextcol)

	for cell in self.get_possible(row, col):
	    self.board[row][col] = cell
	    if self.try_board(nextrow, nextcol):
		return True

	self.board[row][col] = 0
	return False

class AjaxPage(MainPage):

    # For the AJAX handler, just output the puzzle solution without the rest of
    # the page. The Javascript will take care of adding this to the correct
    # place on the page.
    def post(self):
	input = self.request.get('input')

	self.solve_puzzle(input)
	self.response.out.write(nl2br(self.output))

# --- Main section ---

application = webapp.WSGIApplication([ 
    ('/', MainPage), 
    ('/ajax', AjaxPage) ], debug=True)

def main():
    run_wsgi_app(application)

if __name__ == "__main__":
    main()

# vim:set tw=0:

Tags: google app engine, python, sudoku
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 1 comment