Anonymous user
Sudoku: Difference between revisions
m
→{{header|Tailspin}}: update to stricter typing
m (→{{header|Picat}}: Added {{out}}) |
m (→{{header|Tailspin}}: update to stricter typing) |
||
Line 12,877:
<lang tailspin>
templates deduceRemainingDigits
data row
templates findOpenPosition
@:{options: 10};
$ -> \[i;j](when <[](..~$@findOpenPosition.options::raw)> do @findOpenPosition: {row: $i, col: $j, options: $::length}; \) -> !VOID
$@ !
end findOpenPosition
templates selectFirst&{pos:}
def digit: $($pos.row;$pos.col) -> $(1);
$ -> \[i;j](
when <?($i <=$pos.row::raw>)?($j <=$pos.col::raw>)> do $digit !
when <[]?($i <=$pos.row::raw>)
|[]?($j <=$pos.col::raw>)
|[]?(($i-1)~/3 <=($pos.row::raw-1)~/3>)?(($j-1)~/3 <=($pos.col::raw-1)~/3>)> do [$... -> \(when <~=$digit> do $! \)] !
otherwise $ !
\) !
end selectFirst
@: $;
$ -> findOpenPosition -> #
Line 12,905:
-> { $next..., options: $next.options::raw-1} ! \) -> #
end deduceRemainingDigits
test 'internal solver'
def sample: [
Line 12,918:
[3,4,5,2,8,6,1,7,9]
];
assert $sample -> deduceRemainingDigits <=$sample> 'completed puzzle unchanged'
assert [
[[5],3,4,6,7,8,9,1,2],
$sample(2..last)...] -> deduceRemainingDigits <=$sample> 'final digit gets placed'
assert [
[[],3,4,6,7,8,9,1,2],
$sample(2..last)...] -> deduceRemainingDigits <=[]> 'no remaining options returns empty'
assert [
[[5],3,4,6,[2,5,7],8,9,1,[2,5]],
$sample(2..last)...] -> deduceRemainingDigits <=$sample> 'solves 3 digits on row'
assert [
[5,3,4,6,7,8,9,1,2],
Line 12,944:
[3,4,5,2,8,6,1,7,9]
] -> deduceRemainingDigits <=$sample> 'solves 3 digits on column'
assert [
[5,3,[4,6],6,7,8,9,1,2],
Line 12,951:
$sample(4..last)...
] -> deduceRemainingDigits <=$sample> 'solves 3 digits in block'
// This gives a contradiction if 3 gets chosen out of [3,5]
assert [
Line 12,957:
$sample(2..last)...] -> deduceRemainingDigits <=$sample> 'contradiction is backtracked'
end 'internal solver'
composer parseSudoku
[<section>=3]
Line 12,966:
rule dot: <'\.'> -> [1..9 -> '$;']
end parseSudoku
test 'input sudoku'
def parsed:
Line 12,980:
...|419|..5
...|.8.|.79' -> parseSudoku;
assert $parsed <[<[<[]>=9](9)>=9](9)> 'parsed sudoku has 9 rows containing 9 columns of lists'
assert $parsed(1;1) <=['5']> 'a digit'
assert $parsed(1;3) <=['1','2','3','4','5','6','7','8','9']> 'a dot'
end 'input sudoku'
templates solveSudoku
$ -> parseSudoku -> deduceRemainingDigits -> #
Line 12,994:
\) -> '$...;' !
end solveSudoku
test 'sudoku solver'
assert
| |||