Sudoku Solver Requirements
Table of Contents
1 Implementation
Tcl was the language of choice, now it's safe to say Python.
1.1 Python code:
From freepythontips on WordPress, give an uncredited reference to a post on StackOverflow from Bill Barksdale. Look for the "Shortest Sudoku Solver in Python"
import sys
def same_row(i,j): return (i/9 == j/9)
def same_col(i,j): return (i-j) % 9 == 0
def same_block(i,j): return (i/27 == j/27 and i%9/3 == j%9/3)
def r(a):
i = a.find('0')
if i == -1:
sys.exit(a)
excluded_numbers = set()
for j in range(81):
if same_row(i,j) or same_col(i,j) or same_block(i,j):
excluded_numbers.add(a[j])
for m in '123456789':
if m not in excluded_numbers:
r(a[:i]+m+a[i+1:])
if __name__ == '__main__':
if len(sys.argv) == 2 and len(sys.argv[1]) == 81:
r(sys.argv[1])
else:
print 'Usage: python sudoku.py puzzle'
print ' where puzzle is an 81 character string '
print ' representing the puzzle read left-to-right,'
print ' top-to-bottom, and 0 is a blank'
Algorithms to pre-compute the Nbits and ValueOf functions are first, then fill in the "row" function. (The nice thing about Tcl is its command structure, no parsing involved).
A cell address is chosen such that (given N = n x n; if n = 3, N =9) There are N*N Cells. and 3*N initial Ncells: N Columns, Rows, and Squares.
COLUMN = CELL % N ROW = CELL / N SQUARE = COLUMN % n + N * ROW % n
These are the initial list of Ncells for any cell.
2 Data
The first N boards sboard… are all traditional Sudoko.
Since my current major source is the daily Newark Star Ledger, all puzzles with a dash in their name, starting with sboard-150510 also have the property that the two main diagonals are also unique in their elements.
An instrumented version runs in the sud_demo function.
Current judgement: the same_diag function, while it "works" adds too much strain on python's recursion stack. After a few hundred thousand hits at a depth in the 40s, it throws up its hands.
A better starting condition is required. Off the top, changing the line:
for m in '123456789': # from this for m in included_numbers[j] # < to
where included_numbers is a pre-pass, and updated for each cell, of the known allowed numbers in each cell. Though I'm not sure just yet how to maintain it, since since each stack pop will have to re-calculate for all the higher #d cells. Oh well