Sudoku solver in python
Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes (also called blocks or regions) contains the digits from 1 to 9 only one time each. The puzzle setter provides a partially completed grid.
I'm really not a sudoku fan but I love solving problems and sudoku offers you a challenging one. So...here's a the shortest sudoku solver written in python
1 2 3 4 | def r(a):i=a.find('0');~i or exit(a);[m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for j in range(81)]or r(a[:i]+m+a[i+1:])for m in'%d'%5**18] from sys import *;r(argv[1]) |
If you want to test that, save it in a file and use the command line to execute the code. Execute the code as following: python solver.py puzzle - where puzzle is an 81 character string representing the puzzle read left-to-right, top-to-bottom, and 0 is a blank space
python solver.py 530070000600195000098000060800060003400803001700020006060000280000419005000080079 |
The problem with the above code is that is really slow. Here's another one that runs about 100x faster and is less cryptic.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | 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: # At this point, m is not excluded by any row, column, or block, so let's place it and recurse 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' |