Show HN: Solving Sudoku using PHP.(gist.github.com)
gist.github.com
Show HN: Solving Sudoku using PHP.
https://gist.github.com/889044
16 comments
thankyou .. i have asked on stack exchange code review.
http://codereview.stackexchange.com/q/1489/2879
http://codereview.stackexchange.com/q/1489/2879
This is one of the best explanations on how to write an efficient brute-force sudoku solver with constraint propagation, it's in Python but should be perfectly readable.
http://norvig.com/sudoku.html
http://norvig.com/sudoku.html
Well the constraint propagation is quite good. My logic adds one more constraint.
If any of the possible values of a cell is not possible in any of the other conflicting cell than its safe to assume that, that value is the value of this cell.
hope its not confused. check the line 313 to 386 of my code.
If any of the possible values of a cell is not possible in any of the other conflicting cell than its safe to assume that, that value is the value of this cell.
hope its not confused. check the line 313 to 386 of my code.
The bit you're missing is not the propagation, it's the memoisation. Roughly summarised, norvig's alrogithm is:
1. Construct a 9x9 Array of possibility arrays containing the numbers 1-9. 2. When a possibility array is reduced to 1 element, remove this number from all related arrays (row, column, box). 3. Reduce the arrays to 1 number as specified by the initial puzzle. 4. If, after propagation all possibility arrays have 1 item, the puzzle is solved 5. Otherwise,choose one of the shortest possiblity arrays and try a value, backtrack if this leads to an unsolvable puzzle
The key points are the memoisation of possiblities, and choosing cells with the smallest number of possibilities for the search.
1. Construct a 9x9 Array of possibility arrays containing the numbers 1-9. 2. When a possibility array is reduced to 1 element, remove this number from all related arrays (row, column, box). 3. Reduce the arrays to 1 number as specified by the initial puzzle. 4. If, after propagation all possibility arrays have 1 item, the puzzle is solved 5. Otherwise,choose one of the shortest possiblity arrays and try a value, backtrack if this leads to an unsolvable puzzle
The key points are the memoisation of possiblities, and choosing cells with the smallest number of possibilities for the search.
Maybe it's time to look at prolog. :-)
P.s: Sorry for the broken new-lines.
:- use module(library(clpfd)). sudoku(Rs) :- flatten(Rs,Vs), Vs ins 1 .. 9, rows(Rs), columns(Rs), blocks(Rs), label(Vs), maplist(writeln,Rs).
rows(Rs) :- maplist(all distinct,Rs).
columns(Rs) :- columns(9,Rs). columns(0,Rs). columns(N,Rs) :- N > 0, N1 is N-1, maplist(nth0(N1),Rs,X), all distinct(X), columns(N1,Rs).
blocks([A,B,C,D,E,F,G,H,I]) :- blocks(A,B,C), blocks(D,E,F), blocks(G,H,I). blocks([],[],[]). blocks([A,B,C|Bs1],[D,E,F|Bs2],[G,H,I|Bs3]) :- all distinct([A,B,C,D,E,F,G,H,I]), blocks(Bs1,Bs2,Bs3).
:- use module(library(clpfd)). sudoku(Rs) :- flatten(Rs,Vs), Vs ins 1 .. 9, rows(Rs), columns(Rs), blocks(Rs), label(Vs), maplist(writeln,Rs).
rows(Rs) :- maplist(all distinct,Rs).
columns(Rs) :- columns(9,Rs). columns(0,Rs). columns(N,Rs) :- N > 0, N1 is N-1, maplist(nth0(N1),Rs,X), all distinct(X), columns(N1,Rs).
blocks([A,B,C,D,E,F,G,H,I]) :- blocks(A,B,C), blocks(D,E,F), blocks(G,H,I). blocks([],[],[]). blocks([A,B,C|Bs1],[D,E,F|Bs2],[G,H,I|Bs3]) :- all distinct([A,B,C,D,E,F,G,H,I]), blocks(Bs1,Bs2,Bs3).
To post code with newlines and whitespace preserved, prefix each line with four spaces.
http://news.ycombinator.com/formatdoc
http://news.ycombinator.com/formatdoc
thx!
Or APL, like here: http://aplwiki.com/SudokuSolver#The_Final_Function
Though languages like Prolog and APL make brute-forcing suduko trivial, I'm pleased with how little code it took in c#
I put the results on github a while back: http://github.com/AnthonySteele/SudokuSolver/blob/master/Sud...
IMHO the fact that it's fast and not very complex to brute-force Sudoku makes it a lot less interesting as a puzzle for people to solve.
I put the results on github a while back: http://github.com/AnthonySteele/SudokuSolver/blob/master/Sud...
IMHO the fact that it's fast and not very complex to brute-force Sudoku makes it a lot less interesting as a puzzle for people to solve.
[deleted]
Solving sudoku by brute force isn't much of a trick. Solving it using non-guessing techniques is the tricky bit.
When the brute-force method is a simple algorithm and executes very quickly, why bother using other methods?
because brute-force executes very quickly for easy sudoku's but as it gets harder and lesser values are provided it takes too much time.
I have a suduko solver. It is what I consider "brute force", though it does not look any further down boards that do not satisfy the constraints of the game (i.e. values unique in rows, columns, 9-cells). Typically it executes in < 0.5 seconds. Can you supply a "hard" puzzle that will take too much time?
A legal puzzle must have only one valid solution.
Update: I googled for a hard sudoku board, got http://www.forbeginners.info/sudoku-puzzles/hard-1.htm It was brute-forced in 0.038 seconds on my laptop. Code is here: http://github.com/AnthonySteele/SudokuSolver/commit/b953ef97...
A legal puzzle must have only one valid solution.
Update: I googled for a hard sudoku board, got http://www.forbeginners.info/sudoku-puzzles/hard-1.htm It was brute-forced in 0.038 seconds on my laptop. Code is here: http://github.com/AnthonySteele/SudokuSolver/commit/b953ef97...
this is not a brute force trick.. it calculate all possibilities and eliminate others using constraint theories.
[1] http://codereview.stackexchange.com/