Show HN: Solving Sudoku using PHP. (opens in new tab)

(gist.github.com)

8 pointsalienDeveloper15y ago15 comments

15 comments

14 comments · 5 top-level

jojo115y ago· 3 in thread

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).

JonnieCache15y ago

To post code with newlines and whitespace preserved, prefix each line with four spaces.

http://news.ycombinator.com/formatdoc

jojo115y ago

thx!

michael_dorfman15y ago

Or APL, like here: http://aplwiki.com/SudokuSolver#The_Final_Function

wccrawford15y ago· 3 in thread

Solving sudoku by brute force isn't much of a trick. Solving it using non-guessing techniques is the tricky bit.

StrawberryFrog15y ago

When the brute-force method is a simple algorithm and executes very quickly, why bother using other methods?

alienDeveloperOP15y ago

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.

1 more reply

alienDeveloperOP15y ago

this is not a brute force trick.. it calculate all possibilities and eliminate others using constraint theories.

glenjamin15y ago· 2 in thread

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

alienDeveloperOP15y ago

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.

glenjamin15y ago

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.

beaumartinez15y ago· 1 in thread

If you'd like your code reviewed, post it on Stack Exchange Code Review[1].

[1] http://codereview.stackexchange.com/

alienDeveloperOP15y ago

thankyou .. i have asked on stack exchange code review.

http://codereview.stackexchange.com/q/1489/2879

StrawberryFrog15y ago

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.

j / k navigate · click thread line to collapse

15 comments

14 comments · 5 top-level

jojo115y ago· 3 in thread

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).

JonnieCache15y ago

To post code with newlines and whitespace preserved, prefix each line with four spaces.

http://news.ycombinator.com/formatdoc

jojo115y ago

thx!

michael_dorfman15y ago

Or APL, like here: http://aplwiki.com/SudokuSolver#The_Final_Function

wccrawford15y ago· 3 in thread

Solving sudoku by brute force isn't much of a trick. Solving it using non-guessing techniques is the tricky bit.

StrawberryFrog15y ago

When the brute-force method is a simple algorithm and executes very quickly, why bother using other methods?

alienDeveloperOP15y ago

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.

1 more reply

alienDeveloperOP15y ago

this is not a brute force trick.. it calculate all possibilities and eliminate others using constraint theories.

glenjamin15y ago· 2 in thread

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

alienDeveloperOP15y ago

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.

glenjamin15y ago

The bit you're missing is not the propagation, it's the memoisation. Roughly summarised, norvig's alrogithm is:

The key points are the memoisation of possiblities, and choosing cells with the smallest number of possibilities for the search.

beaumartinez15y ago· 1 in thread

If you'd like your code reviewed, post it on Stack Exchange Code Review[1].

[1] http://codereview.stackexchange.com/

alienDeveloperOP15y ago

thankyou .. i have asked on stack exchange code review.

http://codereview.stackexchange.com/q/1489/2879

StrawberryFrog15y ago

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.

j / k navigate · click thread line to collapse