Small Python Simple Sudoku Solution
After a comment from Kevin Greer pointing to his JavaScript solution for Sudoku, I've been looking at Sudokus a little more.
What I Did
I realised that my solution only works for simple sudokus and after seeing Kevin's very small solution, I was challenged to come up with a smaller program that works for all sudokus, but doesn't use a brute-force approach. For now, I've found a much smaller solution - the main solution loop is 6 lines - but it still only works for simple sudokus. It is still using the basic approach of using squares that are already solved to reduce the potential solution set of squares in the same row, column and box. It repeats until all squares are solved.
Small Python Solution for Simple Sudokus.
Kevin's solution seems to use a brute-force approach. To be honest, I can't actually figure out how his program works exactly - it is quite cryptic, or I'm just too dumb. It does work for difficult Sudokus, but I gave up after 3 minutes waiting for it to solve what is claimed to be the hardest Sudoku (below) that I found via Kevin's link to lambda-the-ultimate. In fairness, I think my solution above is quite cryptic and I don't know if I would follow it if I hadn't written it myself.
Hardest Sudoku:
What I Learnt
filter(lamdba x: ..., ...) Using filter() with a lamdba expression allows you to do a lot in one line. I find it fun to write code like this, but it can be difficult to understand. I do think that less code is generally a good idea, but I would always put code maintainability before brevity. If you can get both, then hooray. If I wanted to make my program more maintainable, I'd maybe add a few more comments, but I would definitely split some of the lines into 2 or more lines and assign some intermediate variables with meaningful names. E.g. rather than:
I would do:
It is all about data structures. It is always interesting to see how data structures influence the way you think about a problem and dictate the algorithms that you use. I was actually just reading through the ACM Classics last week. As I recall, I saw Simon Harris write about C. J. Date. While searching to find out more about C. J. Date (who seems to be carrying around some serious issues with how relational databases and SQL have turned out), I came across the ACM Classics. I couldn't find any official list on the ACM website of all the classics, but the ones I found are:
Niklaus Wirth writes about the 8 Queens problem, which funnily enough is equivalent to sudoku and he says:
It struck me how much my code felt like SQL. E.g. for solvedSquare in filter(lambda x: x[grouptype] == r and len(x['s']) == 1, sudoku) feels very similar to select * from sudoku where grouptype=:r and length(s) = 1. It makes me curious to think of what a sudoku solution in PL/SQL would look like. I think it would probably be smaller than any other language.
Anyway, they're just a few of my thoughts.
What I Did
I realised that my solution only works for simple sudokus and after seeing Kevin's very small solution, I was challenged to come up with a smaller program that works for all sudokus, but doesn't use a brute-force approach. For now, I've found a much smaller solution - the main solution loop is 6 lines - but it still only works for simple sudokus. It is still using the basic approach of using squares that are already solved to reduce the potential solution set of squares in the same row, column and box. It repeats until all squares are solved.
Small Python Solution for Simple Sudokus.
#!/bin/python
import sys
f=file(sys.argv[1])
sudoku = []
def display():
for row in range(9):
if (row in (3,6)): print('-' * 31 + '+' + '-' * 32 + '+' + '-' * 32)
for column in range(9):
if (column in (3,6)): sys.stdout.write(' | ')
sys.stdout.write('%10s' % ''.join(filter(lambda x: x['r'] == row and x['c'] == column, sudoku)[0]['s']))
sys.stdout.write('\n')
sys.stdout.write('\n' * 3)
for row, line in enumerate(f.readlines()):
for column, c in enumerate(line.strip()):
solutionSet = '123456789'
if c in solutionSet: solutionSet = c
# r=row, c=column, b=box, s=solutionSet
sudoku += [{'r': row, 'c': column, 'b': (row / 3) * 3 + (column / 3), 's': solutionSet}]
# while some squares are not yet solved - i.e. len(solnSet) > 1
while (len(filter(lambda x: len(x['s']) > 1, sudoku))):
for grouptype in ['r', 'c', 'b']:
for r in range(9):
for solvedSquare in filter(lambda x: x[grouptype] == r and len(x['s']) == 1, sudoku):
for unsolvedSquare in filter(lambda x: x[grouptype] == r and len(x['s']) > 1, sudoku):
unsolvedSquare['s'] = unsolvedSquare['s'].replace(solvedSquare['s'], '')
display()
Kevin's solution seems to use a brute-force approach. To be honest, I can't actually figure out how his program works exactly - it is quite cryptic, or I'm just too dumb. It does work for difficult Sudokus, but I gave up after 3 minutes waiting for it to solve what is claimed to be the hardest Sudoku (below) that I found via Kevin's link to lambda-the-ultimate. In fairness, I think my solution above is quite cryptic and I don't know if I would follow it if I hadn't written it myself.
Hardest Sudoku:
1 0 0 | 0 0 2 | 0 0 0
0 0 0 | 7 4 0 | 5 0 0
0 0 0 | 0 0 0 | 0 0 4
-------+-------+-------
0 3 0 | 7 5 0 | 0 0 0
0 0 0 | 0 0 0 | 0 0 9
0 0 0 | 0 0 0 | 6 0 0
-------+-------+-------
0 4 0 | 0 0 0 | 0 0 0
0 0 6 | 0 0 0 | 0 0 1
0 0 0 | 0 7 1 | 0 3 0
What I Learnt
filter(lamdba x: ..., ...) Using filter() with a lamdba expression allows you to do a lot in one line. I find it fun to write code like this, but it can be difficult to understand. I do think that less code is generally a good idea, but I would always put code maintainability before brevity. If you can get both, then hooray. If I wanted to make my program more maintainable, I'd maybe add a few more comments, but I would definitely split some of the lines into 2 or more lines and assign some intermediate variables with meaningful names. E.g. rather than:
for solvedSquare in filter(lambda x: x[grouptype] == r and len(x['s']) == 1, sudoku):
for unsolvedSquare in filter(lambda x: x[grouptype] == r and len(x['s']) > 1, sudoku):
unsolvedSquare['s'] = unsolvedSquare['s'].replace(solvedSquare['s'], '')
I would do:
# get all squares in the current row, column, or box that are already solvedI don't know. Maybe that makes it worse?
# and remove those values from all other squares in the same row, column, box
solvedSquares = filter(lambda x: x[grouptype] == r and len(x['s']) == 1, sudoku)
for solved in solvedSquares:
unsolvedSquares = filter(lambda x: x[grouptype] == r and len(x['s']) > 1, sudoku)
for unsolved in unsolvedSquares:
unsolved['s'] = unsolved['s'].replace(solved['s'], '')
It is all about data structures. It is always interesting to see how data structures influence the way you think about a problem and dictate the algorithms that you use. I was actually just reading through the ACM Classics last week. As I recall, I saw Simon Harris write about C. J. Date. While searching to find out more about C. J. Date (who seems to be carrying around some serious issues with how relational databases and SQL have turned out), I came across the ACM Classics. I couldn't find any official list on the ACM website of all the classics, but the ones I found are:
- http://www.acm.org/classics/sep95/ - Ken Thompson: Reflections on Trusting Trust
- http://www.acm.org/classics/oct95/ - Edsger W. Dijkstra: Go To Considered Harmful
- http://www.acm.org/classics/nov95/ - E. F. Codd: A Relational Model of Data for Large Shared Data Banks
- http://www.acm.org/classics/dec95/ - Niklaus Wirth: Program Development by Stepwise Refinement
- http://www.acm.org/classics/feb96/ - C. A. R. Hoare: Monitors: An Operating System Structuring Concept
- http://www.acm.org/classics/mar96/ - Edsger W. Dijkstra: The Structure of "THE" - Multiprogramming System Appendix
- http://www.acm.org/classics/apr96/ - Robert M. MetcalfeDavid R. Boggs: Ethernet: Distributed Packet Switching for Local Computer Networks
- http://www.acm.org/classics/may96/ - D. L. Parnas: On the Criteria To Be Used in Decomposing Systems into Modules
Niklaus Wirth writes about the 8 Queens problem, which funnily enough is equivalent to sudoku and he says:
The success of an algorithm, however, depends almost always on a suitable choice of its data representation in the light of the ease in which this representation allows the necessary operations to be expressed.In my new solution, I have changed the data structure from a 2-dimensional array, where each element of the array contains a vector of possible solutions for that square to a single list of dictionaries. Each dictionary represents a square on the board. The dictionary contains its row (key 'r'), column (key 'c') and box (key 'b') along with its solution set (key 's') represented as a string. The resulting data structure makes it easy to make the code concise by taking advantage of the previously mentioned filter() and lambda expressions.
It struck me how much my code felt like SQL. E.g. for solvedSquare in filter(lambda x: x[grouptype] == r and len(x['s']) == 1, sudoku) feels very similar to select * from sudoku where grouptype=:r and length(s) = 1. It makes me curious to think of what a sudoku solution in PL/SQL would look like. I think it would probably be smaller than any other language.
Anyway, they're just a few of my thoughts.
0 Comments:
Post a Comment
<< Home