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.
Show HN: Solving Sudoku using PHP.
11–17 of 17 posts
Re: Show HN: Solving Sudoku using PHP.
#12Solving 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.
Re: Show HN: Solving Sudoku using PHP.
#13Maybe 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]…
To post code with newlines and whitespace preserved, prefix each line with four spaces. http://news.ycombinator.com/formatdoc
thx!
Re: Show HN: Solving Sudoku using PHP.
#14[deleted]
Re: Show HN: Solving Sudoku using PHP.
#15This 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
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.
Re: Show HN: Solving Sudoku using PHP.
#16This 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
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.
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.
Re: Show HN: Solving Sudoku using PHP.
#17Earlier quoted context omitted.
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 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...