Sudoku: Difference between revisions
Content added Content deleted
(Sudoku Solver Implementation in Crystal) |
|||
Line 9,178: | Line 9,178: | ||
7 8 2 | 5 6 3 | 9 1 4 |
7 8 2 | 5 6 3 | 9 1 4 |
||
(solved in 0.027s) |
(solved in 0.027s) |
||
</pre> |
|||
=={{header|Picat}}== |
|||
Using constraint programming. |
|||
<lang picat>import util. |
|||
import cp. |
|||
main => go. |
|||
go => |
|||
sudokus(Sudokus), |
|||
foreach([Comment,SudokuS] in Sudokus) |
|||
println(SudokuS), |
|||
println(Comment), |
|||
% Convert string to numbers and "." to _ (unknown) |
|||
Sudoku = [ [cond(S == '.',_,S.to_integer()) : |
|||
S in slice(SudokuS,(I*9)+1,(I+1)*9)] : I in 0..8], |
|||
print_board(Sudoku), |
|||
% Ensure unicity of the solution (check that it is a unique solution) |
|||
All = findall(Sudoku,sudoku(Sudoku)), |
|||
if All.length > 1 then |
|||
printf("Problem has %d solutions!\n", All.length) |
|||
end, |
|||
print("Solution:") |
|||
foreach(A in All) |
|||
print_board(A) |
|||
end, |
|||
nl |
|||
end, |
|||
nl. |
|||
sudoku(Board) => |
|||
N = ceiling(sqrt(Board.len)), |
|||
N2 = N*N, |
|||
Vars = Board.vars(), |
|||
Vars :: 1..N2, |
|||
foreach(Row in Board) all_different(Row) end, |
|||
foreach(Column in transpose(Board)) all_different(Column) end, |
|||
foreach(I in 1..N..N2, J in 1..N..N2) |
|||
all_different([Board[I+K,J+L] : K in 0..N-1, L in 0..N-1]) |
|||
end, |
|||
solve([ffd,inout], Vars). |
|||
print_board(Board) => |
|||
N = Board.length, |
|||
foreach(I in 1..N) |
|||
foreach(J in 1..N) |
|||
X = Board[I,J], |
|||
if var(X) then printf(" _") else printf(" %w", X) end |
|||
end, |
|||
nl |
|||
end, |
|||
nl. |
|||
% (Problems from the Groovy implementation) |
|||
sudokus(Sudokus) => Sudokus = |
|||
[ |
|||
"819..5.....2...75..371.4.6.4..59.1..7..3.8..2..3.62..7.5.7.921..64...9.....2..438", |
|||
"53..247....2...8..1..7.39.2..8.72.49.2.98..7.79.....8.....3.5.696..1.3...5.69..1.", |
|||
"..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..", |
|||
"394..267....3..4..5..69..2..45...9..6.......7..7...58..1..67..8..9..8....264..735", |
|||
"97.3...6..6.75.........8.5.......67.....3.....539..2..7...25.....2.1...8.4...73..", |
|||
"4......6.5...8.9..3....1....2.7....1.9.....4.8....3.5....2....7..6.5...8.1......6", |
|||
"85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.", |
|||
"..1..5.7.92.6.......8...6...9..2.4.1.........3.4.8..9...7...3.......7.69.1.8..7..", |
|||
".9...4..7.....79..8........4.58.....3.......2.....97.6........4..35.....2..6...8.", |
|||
"12.3....435....1....4........54..2..6...7.........8.9...31..5.......9.7.....6...8", |
|||
"9..2..5...4..6..3...3.....6...9..2......5..8...7..4..37.....1...5..2..4...1..6..9", |
|||
"1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..", |
|||
"12.4..3..3...1..5...6...1..7...9.....4.6.3.....3..2...5...8.7....7.....5.......98", |
|||
"..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9", |
|||
".......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....", |
|||
"....839..1......3...4....7..42.3....6.......4....7..1..2........8...92.....25...6", |
|||
"..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686........7..6..5.." |
|||
]. |
|||
</lang> |
|||
Output. All problems are solved (and proved/checked for unicity) in 0.043s. |
|||
<pre> |
|||
819..5.....2...75..371.4.6.4..59.1..7..3.8..2..3.62..7.5.7.921..64...9.....2..438 |
|||
8 1 9 _ _ 5 _ _ _ |
|||
_ _ 2 _ _ _ 7 5 _ |
|||
_ 3 7 1 _ 4 _ 6 _ |
|||
4 _ _ 5 9 _ 1 _ _ |
|||
7 _ _ 3 _ 8 _ _ 2 |
|||
_ _ 3 _ 6 2 _ _ 7 |
|||
_ 5 _ 7 _ 9 2 1 _ |
|||
_ 6 4 _ _ _ 9 _ _ |
|||
_ _ _ 2 _ _ 4 3 8 |
|||
Solution: |
|||
8 1 9 6 7 5 3 2 4 |
|||
6 4 2 9 8 3 7 5 1 |
|||
5 3 7 1 2 4 8 6 9 |
|||
4 2 6 5 9 7 1 8 3 |
|||
7 9 5 3 1 8 6 4 2 |
|||
1 8 3 4 6 2 5 9 7 |
|||
3 5 8 7 4 9 2 1 6 |
|||
2 6 4 8 3 1 9 7 5 |
|||
9 7 1 2 5 6 4 3 8 |
|||
... |
|||
</pre> |
</pre> |
||