Sudoku: Difference between revisions
Content deleted Content added
Add reference. |
Thundergnat (talk | contribs) Rename Perl 6 -> Raku, alphabetize, minor clean-up |
||
Line 401: | Line 401: | ||
return r |
return r |
||
}</lang> |
}</lang> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<lang AWK> |
<lang AWK> |
||
Line 1,452: | Line 1,453: | ||
}</lang> |
}</lang> |
||
=={{header|C#}}== |
=={{header|C sharp|C#}}== |
||
===“Manual” Solution=== |
===“Manual” Solution=== |
||
{{trans|Java}} |
{{trans|Java}} |
||
Line 3,708: | Line 3,709: | ||
1|7|3|6|9|4|8|5|2| |
1|7|3|6|9|4|8|5|2| |
||
</pre> |
</pre> |
||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
{{works with|4tH|3.60.0}} |
{{works with|4tH|3.60.0}} |
||
Line 5,277: | Line 5,279: | ||
} |
} |
||
}</lang> |
}</lang> |
||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
Line 5,815: | Line 5,815: | ||
5 9 8 | 7 3 6 | 2 4 1 |
5 9 8 | 7 3 6 | 2 4 1 |
||
</pre> |
</pre> |
||
=={{header|Nim}}== |
|||
{{trans|Kotlin}} |
|||
<lang nim>{.this: self.} |
|||
type |
|||
Sudoku = ref object |
|||
grid : array[81, int] |
|||
solved : bool |
|||
proc `$`(self: Sudoku): string = |
|||
var sb: string = "" |
|||
for i in 0..8: |
|||
for j in 0..8: |
|||
sb &= $grid[i * 9 + j] |
|||
sb &= " " |
|||
if j == 2 or j == 5: |
|||
sb &= "| " |
|||
sb &= "\n" |
|||
if i == 2 or i == 5: |
|||
sb &= "------+------+------\n" |
|||
sb |
|||
proc init(self: Sudoku, rows: array[9, string]) = |
|||
for i in 0..8: |
|||
for j in 0..8: |
|||
grid[9 * i + j] = rows[i][j].int - '0'.int |
|||
proc checkValidity(self: Sudoku, v, x, y: int): bool = |
|||
for i in 0..8: |
|||
if grid[y * 9 + i] == v or grid[i * 9 + x] == v: |
|||
return false |
|||
var startX = (x div 3) * 3 |
|||
var startY = (y div 3) * 3 |
|||
for i in startY..startY + 2: |
|||
for j in startX..startX + 2: |
|||
if grid[i * 9 + j] == v: |
|||
return false |
|||
result = true |
|||
proc placeNumber(self: Sudoku, pos: int) = |
|||
if solved: |
|||
return |
|||
if pos == 81: |
|||
solved = true |
|||
return |
|||
if grid[pos] > 0: |
|||
placeNumber(pos + 1) |
|||
return |
|||
for n in 1..9: |
|||
if checkValidity(n, pos mod 9, pos div 9): |
|||
grid[pos] = n |
|||
placeNumber(pos + 1) |
|||
if solved: |
|||
return |
|||
grid[pos] = 0 |
|||
proc solve(self: Sudoku) = |
|||
echo "Starting grid:\n\n", $self |
|||
placeNumber(0) |
|||
if solved: |
|||
echo "Solution:\n\n", $self |
|||
else: |
|||
echo "Unsolvable!" |
|||
var rows = ["850002400", |
|||
"720000009", |
|||
"004000000", |
|||
"000107002", |
|||
"305000900", |
|||
"040000000", |
|||
"000080070", |
|||
"017000000", |
|||
"000036040"] |
|||
var puzzle = Sudoku() |
|||
puzzle.init(rows) |
|||
puzzle.solve()</lang> |
|||
{{out}} |
|||
<pre>Starting grid: |
|||
8 5 0 | 0 0 2 | 4 0 0 |
|||
7 2 0 | 0 0 0 | 0 0 9 |
|||
0 0 4 | 0 0 0 | 0 0 0 |
|||
------+-------+------ |
|||
0 0 0 | 1 0 7 | 0 0 2 |
|||
3 0 5 | 0 0 0 | 9 0 0 |
|||
0 4 0 | 0 0 0 | 0 0 0 |
|||
------+-------+------ |
|||
0 0 0 | 0 8 0 | 0 7 0 |
|||
0 1 7 | 0 0 0 | 0 0 0 |
|||
0 0 0 | 0 3 6 | 0 4 0 |
|||
Solution: |
|||
8 5 9 | 6 1 2 | 4 3 7 |
|||
7 2 3 | 8 5 4 | 1 6 9 |
|||
1 6 4 | 3 7 9 | 5 2 8 |
|||
------+-------+------ |
|||
9 8 6 | 1 4 7 | 3 5 2 |
|||
3 7 5 | 2 6 8 | 9 1 4 |
|||
2 4 1 | 5 9 3 | 7 8 6 |
|||
------+-------+------ |
|||
4 3 2 | 9 8 1 | 6 7 5 |
|||
6 1 7 | 4 2 5 | 8 9 3 |
|||
5 9 8 | 7 3 6 | 2 4 1</pre> |
|||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
Line 6,632: | Line 6,525: | ||
5 8 1 3 6 9 2 4 7 |
5 8 1 3 6 9 2 4 7 |
||
4 7 3 2 5 8 1 9 6</lang> |
4 7 3 2 5 8 1 9 6</lang> |
||
=={{header|Nim}}== |
|||
{{trans|Kotlin}} |
|||
<lang nim>{.this: self.} |
|||
type |
|||
Sudoku = ref object |
|||
grid : array[81, int] |
|||
solved : bool |
|||
proc `$`(self: Sudoku): string = |
|||
var sb: string = "" |
|||
for i in 0..8: |
|||
for j in 0..8: |
|||
sb &= $grid[i * 9 + j] |
|||
sb &= " " |
|||
if j == 2 or j == 5: |
|||
sb &= "| " |
|||
sb &= "\n" |
|||
if i == 2 or i == 5: |
|||
sb &= "------+------+------\n" |
|||
sb |
|||
proc init(self: Sudoku, rows: array[9, string]) = |
|||
for i in 0..8: |
|||
for j in 0..8: |
|||
grid[9 * i + j] = rows[i][j].int - '0'.int |
|||
proc checkValidity(self: Sudoku, v, x, y: int): bool = |
|||
for i in 0..8: |
|||
if grid[y * 9 + i] == v or grid[i * 9 + x] == v: |
|||
return false |
|||
var startX = (x div 3) * 3 |
|||
var startY = (y div 3) * 3 |
|||
for i in startY..startY + 2: |
|||
for j in startX..startX + 2: |
|||
if grid[i * 9 + j] == v: |
|||
return false |
|||
result = true |
|||
proc placeNumber(self: Sudoku, pos: int) = |
|||
if solved: |
|||
return |
|||
if pos == 81: |
|||
solved = true |
|||
return |
|||
if grid[pos] > 0: |
|||
placeNumber(pos + 1) |
|||
return |
|||
for n in 1..9: |
|||
if checkValidity(n, pos mod 9, pos div 9): |
|||
grid[pos] = n |
|||
placeNumber(pos + 1) |
|||
if solved: |
|||
return |
|||
grid[pos] = 0 |
|||
proc solve(self: Sudoku) = |
|||
echo "Starting grid:\n\n", $self |
|||
placeNumber(0) |
|||
if solved: |
|||
echo "Solution:\n\n", $self |
|||
else: |
|||
echo "Unsolvable!" |
|||
var rows = ["850002400", |
|||
"720000009", |
|||
"004000000", |
|||
"000107002", |
|||
"305000900", |
|||
"040000000", |
|||
"000080070", |
|||
"017000000", |
|||
"000036040"] |
|||
var puzzle = Sudoku() |
|||
puzzle.init(rows) |
|||
puzzle.solve()</lang> |
|||
{{out}} |
|||
<pre>Starting grid: |
|||
8 5 0 | 0 0 2 | 4 0 0 |
|||
7 2 0 | 0 0 0 | 0 0 9 |
|||
0 0 4 | 0 0 0 | 0 0 0 |
|||
------+-------+------ |
|||
0 0 0 | 1 0 7 | 0 0 2 |
|||
3 0 5 | 0 0 0 | 9 0 0 |
|||
0 4 0 | 0 0 0 | 0 0 0 |
|||
------+-------+------ |
|||
0 0 0 | 0 8 0 | 0 7 0 |
|||
0 1 7 | 0 0 0 | 0 0 0 |
|||
0 0 0 | 0 3 6 | 0 4 0 |
|||
Solution: |
|||
8 5 9 | 6 1 2 | 4 3 7 |
|||
7 2 3 | 8 5 4 | 1 6 9 |
|||
1 6 4 | 3 7 9 | 5 2 8 |
|||
------+-------+------ |
|||
9 8 6 | 1 4 7 | 3 5 2 |
|||
3 7 5 | 2 6 8 | 9 1 4 |
|||
2 4 1 | 5 9 3 | 7 8 6 |
|||
------+-------+------ |
|||
4 3 2 | 9 8 1 | 6 7 5 |
|||
6 1 7 | 4 2 5 | 8 9 3 |
|||
5 9 8 | 7 3 6 | 2 4 1</pre> |
|||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
Line 6,792: | Line 6,792: | ||
in |
in |
||
{Inspect {Solve Puzzle1}.1}</lang> |
{Inspect {Solve Puzzle1}.1}</lang> |
||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
Line 7,244: | Line 7,243: | ||
9 6 7|4 1 5|3 2 8 |
9 6 7|4 1 5|3 2 8 |
||
2 5 3|6 9 8|4 1 7 |
2 5 3|6 9 8|4 1 7 |
||
</pre> |
|||
=={{header|Perl 6}}== |
|||
{{trans|Perl}} |
|||
<lang perl6>use v6; |
|||
my @A = < |
|||
5 3 0 0 2 4 7 0 0 |
|||
0 0 2 0 0 0 8 0 0 |
|||
1 0 0 7 0 3 9 0 2 |
|||
0 0 8 0 7 2 0 4 9 |
|||
0 2 0 9 8 0 0 7 0 |
|||
7 9 0 0 0 0 0 8 0 |
|||
0 0 0 0 3 0 5 0 6 |
|||
9 6 0 0 1 0 3 0 0 |
|||
0 5 0 6 9 0 0 1 0 |
|||
>; |
|||
my &I = * div 9; # line number |
|||
my &J = * % 9; # column number |
|||
my &K = { ($_ div 27) * 3 + $_ % 9 div 3 }; # bloc number |
|||
sub solve { |
|||
for ^@A -> $i { |
|||
next if @A[$i]; |
|||
my @taken-values = @A[ |
|||
grep { |
|||
I($_) == I($i) || J($_) == J($i) || K($_) == K($i) |
|||
}, ^@A |
|||
]; |
|||
for grep none(@taken-values), 1..9 { |
|||
@A[$i] = $_; |
|||
solve; |
|||
} |
|||
return @A[$i] = 0; |
|||
} |
|||
my $i = 1; |
|||
for ^@A { |
|||
print "@A[$_] "; |
|||
print " " if $i %% 3; |
|||
print "\n" if $i %% 9; |
|||
print "\n" if $i++ %% 27; |
|||
} |
|||
} |
|||
solve;</lang> |
|||
{{out}} |
|||
<pre>5 3 9 8 2 4 7 6 1 |
|||
6 7 2 1 5 9 8 3 4 |
|||
1 8 4 7 6 3 9 5 2 |
|||
3 1 8 5 7 2 6 4 9 |
|||
4 2 5 9 8 6 1 7 3 |
|||
7 9 6 3 4 1 2 8 5 |
|||
8 4 1 2 3 7 5 9 6 |
|||
9 6 7 4 1 5 3 2 8 |
|||
2 5 3 6 9 8 4 1 7</pre> |
|||
This is an alternative solution that uses a more ellaborate set of choices instead of brute-forcing it. |
|||
<lang perl6>#!/usr/bin/env perl6 |
|||
use v6; |
|||
# |
|||
# In this code, a sudoku puzzle is represented as a two-dimentional |
|||
# array. The cells that are not yet solved are represented by yet |
|||
# another array of all the possible values. |
|||
# |
|||
# This implementation is not a simple brute force evaluation of all |
|||
# the options, but rather makes four extra attempts to guide the |
|||
# solution: |
|||
# |
|||
# 1) For every change in the grid, usually made by an attempt at a |
|||
# solution, we will reduce the search space of the possible values |
|||
# in all the other cells before going forward. |
|||
# |
|||
# 2) When a cell that is not yet resolved is the only one that can |
|||
# hold a specific value, resolve it immediately instead of |
|||
# performing the regular search. |
|||
# |
|||
# 3) Instead of trying from cell 1,1 and moving in sequence, this |
|||
# implementation will start trying on the cell that is the closest |
|||
# to being solved already. |
|||
# |
|||
# 4) Instead of trying all possible values in sequence, start with |
|||
# the value that is the most unique. I.e.: If the options for this |
|||
# cell are 1,4,6 and 6 is only a candidate for two of the |
|||
# competing cells, we start with that one. |
|||
# |
|||
# keep a list with all the cells, handy for traversal |
|||
my @cells = do for (flat 0..8 X 0..8) -> $x, $y { [ $x, $y ] }; |
|||
# |
|||
# Try to solve this puzzle and return the resolved puzzle if it is at |
|||
# all solvable in this configuration. |
|||
sub solve($sudoku, Int $level) { |
|||
# cleanup the impossible values first, |
|||
if (cleanup-impossible-values($sudoku, $level)) { |
|||
# try to find implicit answers |
|||
while (find-implicit-answers($sudoku, $level)) { |
|||
# and every time you find some, re-do the cleanup and try again |
|||
cleanup-impossible-values($sudoku, $level); |
|||
} |
|||
# Now let's actually try to solve a new value. But instead of |
|||
# going in sequence, we select the cell that is the closest to |
|||
# being solved already. This will reduce the overall number of |
|||
# guesses. |
|||
for sort { solution-complexity-factor($sudoku, $_[0], $_[1]) }, |
|||
grep { $sudoku[$_[0]][$_[1]] ~~ Array }, |
|||
@cells -> $cell |
|||
{ |
|||
my Int ($x, $y) = @($cell); |
|||
# Now let's try the possible values in the order of |
|||
# uniqueness. |
|||
for sort { matches-in-competing-cells($sudoku, $x, $y, $_) }, @($sudoku[$x][$y]) -> $val { |
|||
trace $level, "Trying $val on "~($x+1)~","~($y+1)~" "~$sudoku[$x][$y].perl; |
|||
my $solution = clone-sudoku($sudoku); |
|||
$solution[$x][$y] = $val; |
|||
my $solved = solve($solution, $level+1); |
|||
if $solved { |
|||
trace $level, "Solved... ($val on "~($x+1)~","~($y+1)~")"; |
|||
return $solved; |
|||
} |
|||
} |
|||
# if we fell through, it means that we found no valid |
|||
# value for this cell |
|||
trace $level, "Backtrack, path unsolvable... (on "~($x+1)~" "~($y+1)~")"; |
|||
return 0; |
|||
} |
|||
# all cells are already solved. |
|||
return $sudoku; |
|||
} else { |
|||
# if the cleanup failed, it means this is an invalid grid. |
|||
return False; |
|||
} |
|||
} |
|||
# This function reduces the search space from values that are already |
|||
# assigned to competing cells. |
|||
sub cleanup-impossible-values($sudoku, Int $level = 1) { |
|||
my Bool $resolved; |
|||
repeat { |
|||
$resolved = False; |
|||
for grep { $sudoku[$_[0]][$_[1]] ~~ Array }, |
|||
@cells -> $cell { |
|||
my Int ($x, $y) = @($cell); |
|||
# which block is this cell in |
|||
my Int $bx = Int($x / 3); |
|||
my Int $by = Int($y / 3); |
|||
# A unfilled cell is not resolved, so it shouldn't match |
|||
my multi match-resolved-cell(Array $other, Int $this) { |
|||
return 0; |
|||
} |
|||
my multi match-resolved-cell(Int $other, Int $this) { |
|||
return $other == $this; |
|||
} |
|||
# Reduce the possible values to the ones that are still |
|||
# valid |
|||
my @r = |
|||
grep { !match-resolved-cell($sudoku[any(0..2)+3*$bx][any(0..2)+3*$by], $_) }, # same block |
|||
grep { !match-resolved-cell($sudoku[any(0..8)][$y], $_) }, # same line |
|||
grep { !match-resolved-cell($sudoku[$x][any(0..8)], $_) }, # same column |
|||
@($sudoku[$x][$y]); |
|||
if (@r.elems == 1) { |
|||
# if only one element is left, then make it resolved |
|||
$sudoku[$x][$y] = @r[0]; |
|||
$resolved = True; |
|||
} elsif (@r.elems == 0) { |
|||
# This is an invalid grid |
|||
return 0; |
|||
} else { |
|||
$sudoku[$x][$y] = @r; |
|||
} |
|||
} |
|||
} while $resolved; # repeat if there was any change |
|||
return 1; |
|||
} |
|||
sub solution-complexity-factor($sudoku, Int $x, Int $y) { |
|||
my Int $bx = Int($x / 3); # this block |
|||
my Int $by = Int($y / 3); |
|||
my multi count-values(Array $val) { |
|||
return $val.elems; |
|||
} |
|||
my multi count-values(Int $val) { |
|||
return 1; |
|||
} |
|||
# the number of possible values should take precedence |
|||
my Int $f = 1000 * count-values($sudoku[$x][$y]); |
|||
for (flat 0..2 X 0..2) -> $lx, $ly { |
|||
$f += count-values($sudoku[$lx+$bx*3][$ly+$by*3]) |
|||
} |
|||
for 0..^($by*3), (($by+1)*3)..8 -> $ly { |
|||
$f += count-values($sudoku[$x][$ly]) |
|||
} |
|||
for 0..^($bx*3), (($bx+1)*3)..8 -> $lx { |
|||
$f += count-values($sudoku[$lx][$y]) |
|||
} |
|||
return $f; |
|||
} |
|||
sub matches-in-competing-cells($sudoku, Int $x, Int $y, Int $val) { |
|||
my Int $bx = Int($x / 3); # this block |
|||
my Int $by = Int($y / 3); |
|||
# Function to decide which possible value to try first |
|||
my multi cell-matching(Int $cell) { |
|||
return $val == $cell ?? 1 !! 0; |
|||
} |
|||
my multi cell-matching(Array $cell) { |
|||
return $cell.grep({ $val == $_ }) ?? 1 !! 0; |
|||
} |
|||
my Int $c = 0; |
|||
for (flat 0..2 X 0..2) -> $lx, $ly { |
|||
$c += cell-matching($sudoku[$lx+$bx*3][$ly+$by*3]) |
|||
} |
|||
for 0..^($by*3), (($by+1)*3)..8 -> $ly { |
|||
$c += cell-matching($sudoku[$x][$ly]) |
|||
} |
|||
for 0..^($bx*3), (($bx+1)*3)..8 -> $lx { |
|||
$c += cell-matching($sudoku[$lx][$y]) |
|||
} |
|||
return $c; |
|||
} |
|||
sub find-implicit-answers($sudoku, Int $level) { |
|||
my Bool $resolved = False; |
|||
for grep { $sudoku[$_[0]][$_[1]] ~~ Array }, |
|||
@cells -> $cell { |
|||
my Int ($x, $y) = @($cell); |
|||
for @($sudoku[$x][$y]) -> $val { |
|||
# If this is the only cell with this val as a possibility, |
|||
# just make it resolved already |
|||
if (matches-in-competing-cells($sudoku, $x, $y, $val) == 1) { |
|||
$sudoku[$x][$y] = $val; |
|||
$resolved = True; |
|||
} |
|||
} |
|||
} |
|||
return $resolved; |
|||
} |
|||
my $puzzle = |
|||
map { [ map { $_ == 0 ?? [1..9] !! $_+0 }, @($_) ] }, |
|||
[ 0,0,0,0,3,7,6,0,0 ], |
|||
[ 0,0,0,6,0,0,0,9,0 ], |
|||
[ 0,0,8,0,0,0,0,0,4 ], |
|||
[ 0,9,0,0,0,0,0,0,1 ], |
|||
[ 6,0,0,0,0,0,0,0,9 ], |
|||
[ 3,0,0,0,0,0,0,4,0 ], |
|||
[ 7,0,0,0,0,0,8,0,0 ], |
|||
[ 0,1,0,0,0,9,0,0,0 ], |
|||
[ 0,0,2,5,4,0,0,0,0 ]; |
|||
my $solved = solve($puzzle, 0); |
|||
if $solved { |
|||
print-sudoku($solved,0); |
|||
} else { |
|||
say "unsolvable."; |
|||
} |
|||
# Utility functions, not really part of the solution |
|||
sub trace(Int $level, Str $message) { |
|||
say '.' x $level, $message; |
|||
} |
|||
sub clone-sudoku($sudoku) { |
|||
my $clone; |
|||
for (flat 0..8 X 0..8) -> $x, $y { |
|||
$clone[$x][$y] = $sudoku[$x][$y]; |
|||
} |
|||
return $clone; |
|||
} |
|||
sub print-sudoku($sudoku, Int $level = 1) { |
|||
trace $level, '-' x 5*9; |
|||
for @($sudoku) -> $row { |
|||
trace $level, join " ", do for @($row) -> $cell { |
|||
$cell ~~ Array ?? "#{$cell.elems}#" !! " $cell " |
|||
} |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
Trying 8 on 9,1 [8, 9] |
|||
.Trying 6 on 9,2 [3, 6] |
|||
..Trying 7 on 9,9 [3, 7] |
|||
...Trying 1 on 9,8 [1, 3] |
|||
....Trying 4 on 8,1 [4, 5] |
|||
.....Trying 3 on 7,2 [3, 5] |
|||
......Trying 3 on 8,7 [2, 3] |
|||
.......Trying 6 on 8,9 [2, 6] |
|||
.......Trying 2 on 8,9 [2, 6] |
|||
.......Backtrack, path unsolvable... (on 8 9) |
|||
......Trying 2 on 8,7 [2, 3] |
|||
.......Trying 3 on 8,9 [3, 6] |
|||
.......Trying 6 on 8,9 [3, 6] |
|||
.......Backtrack, path unsolvable... (on 8 9) |
|||
......Backtrack, path unsolvable... (on 8 7) |
|||
.....Trying 5 on 7,2 [3, 5] |
|||
......Trying 5 on 8,7 [2, 5] |
|||
.......Trying 6 on 8,9 [2, 6] |
|||
.......Trying 2 on 8,9 [2, 6] |
|||
.......Backtrack, path unsolvable... (on 8 9) |
|||
......Trying 2 on 8,7 [2, 5] |
|||
.......Trying 5 on 8,9 [5, 6] |
|||
.......Trying 6 on 8,9 [5, 6] |
|||
.......Backtrack, path unsolvable... (on 8 9) |
|||
......Backtrack, path unsolvable... (on 8 7) |
|||
.....Backtrack, path unsolvable... (on 7 2) |
|||
....Trying 5 on 8,1 [4, 5] |
|||
.....Trying 3 on 8,3 [3, 4] |
|||
......Trying 6 on 8,9 [2, 6] |
|||
.......Trying 3 on 7,9 [3, 5] |
|||
........Trying 5 on 1,9 [2, 5] |
|||
.........Trying 3 on 3,8 [3, 7] |
|||
..........Trying 4 on 2,1 [1, 4] |
|||
..........Trying 1 on 2,1 [1, 4] |
|||
..........Backtrack, path unsolvable... (on 2 1) |
|||
.........Trying 7 on 3,8 [3, 7] |
|||
..........Trying 3 on 3,7 [1, 3] |
|||
..........Trying 1 on 3,7 [1, 3] |
|||
..........Backtrack, path unsolvable... (on 3 7) |
|||
.........Backtrack, path unsolvable... (on 3 8) |
|||
........Trying 2 on 1,9 [2, 5] |
|||
.........Trying 3 on 3,8 [3, 7] |
|||
..........Trying 7 on 2,7 [1, 7] |
|||
...........Trying 9 on 3,1 [2, 9] |
|||
...........Trying 2 on 3,1 [2, 9] |
|||
...........Backtrack, path unsolvable... (on 3 1) |
|||
..........Trying 1 on 2,7 [1, 7] |
|||
..........Backtrack, path unsolvable... (on 2 7) |
|||
.........Trying 7 on 3,8 [3, 7] |
|||
..........Trying 3 on 3,7 [1, 3] |
|||
..........Trying 1 on 3,7 [1, 3] |
|||
...........Trying 9 on 3,1 [2, 9] |
|||
...........Trying 2 on 3,1 [2, 9] |
|||
...........Backtrack, path unsolvable... (on 3 1) |
|||
..........Backtrack, path unsolvable... (on 3 7) |
|||
.........Backtrack, path unsolvable... (on 3 8) |
|||
........Backtrack, path unsolvable... (on 1 9) |
|||
.......Trying 5 on 7,9 [3, 5] |
|||
........Trying 8 on 1,9 [2, 8] |
|||
.........Trying 2 on 3,7 [1, 2] |
|||
.........Trying 1 on 3,7 [1, 2] |
|||
.........Backtrack, path unsolvable... (on 3 7) |
|||
........Trying 2 on 1,9 [2, 8] |
|||
.........Trying 7 on 3,8 [5, 7] |
|||
..........Trying 5 on 3,7 [1, 5] |
|||
...........Trying 2 on 2,1 [2, 4] |
|||
...........Trying 4 on 2,1 [2, 4] |
|||
...........Backtrack, path unsolvable... (on 2 1) |
|||
..........Trying 1 on 3,7 [1, 5] |
|||
...........Trying 9 on 3,1 [2, 9] |
|||
...........Trying 2 on 3,1 [2, 9] |
|||
...........Backtrack, path unsolvable... (on 3 1) |
|||
..........Backtrack, path unsolvable... (on 3 7) |
|||
.........Trying 5 on 3,8 [5, 7] |
|||
..........Trying 7 on 3,7 [1, 7] |
|||
...........Trying 2 on 2,1 [2, 4] |
|||
...........Trying 4 on 2,1 [2, 4] |
|||
...........Backtrack, path unsolvable... (on 2 1) |
|||
..........Trying 1 on 3,7 [1, 7] |
|||
..........Backtrack, path unsolvable... (on 3 7) |
|||
.........Backtrack, path unsolvable... (on 3 8) |
|||
........Backtrack, path unsolvable... (on 1 9) |
|||
.......Backtrack, path unsolvable... (on 7 9) |
|||
......Trying 2 on 8,9 [2, 6] |
|||
.......Trying 3 on 7,9 [3, 5] |
|||
........Trying 8 on 1,9 [5, 8] |
|||
.........Trying 3 on 3,8 [3, 7] |
|||
..........Trying 4 on 1,3 [1, 4] |
|||
...........Trying 9 on 1,1 [1, 9] |
|||
............Trying 1 on 3,1 [1, 2] |
|||
............Trying 2 on 3,1 [1, 2] |
|||
............Backtrack, path unsolvable... (on 3 1) |
|||
...........Trying 1 on 1,1 [1, 9] |
|||
...........Backtrack, path unsolvable... (on 1 1) |
|||
..........Trying 1 on 1,3 [1, 4] |
|||
...........Trying 9 on 1,1 [4, 9] |
|||
...........Trying 4 on 1,1 [4, 9] |
|||
...........Backtrack, path unsolvable... (on 1 1) |
|||
..........Backtrack, path unsolvable... (on 1 3) |
|||
.........Trying 7 on 3,8 [3, 7] |
|||
..........Trying 3 on 3,7 [1, 3] |
|||
..........Trying 1 on 3,7 [1, 3] |
|||
...........Trying 9 on 3,1 [2, 9] |
|||
...........Trying 2 on 3,1 [2, 9] |
|||
...........Backtrack, path unsolvable... (on 3 1) |
|||
..........Backtrack, path unsolvable... (on 3 7) |
|||
.........Backtrack, path unsolvable... (on 3 8) |
|||
........Trying 5 on 1,9 [5, 8] |
|||
........Backtrack, path unsolvable... (on 1 9) |
|||
.......Trying 5 on 7,9 [3, 5] |
|||
........Trying 5 on 1,8 [2, 5] |
|||
.........Trying 7 on 3,8 [2, 7] |
|||
..........Trying 4 on 1,3 [1, 4] |
|||
..........Trying 1 on 1,3 [1, 4] |
|||
..........Backtrack, path unsolvable... (on 1 3) |
|||
.........Trying 2 on 3,8 [2, 7] |
|||
..........Trying 9 on 3,1 [1, 9] |
|||
..........Trying 1 on 3,1 [1, 9] |
|||
..........Backtrack, path unsolvable... (on 3 1) |
|||
.........Backtrack, path unsolvable... (on 3 8) |
|||
........Trying 2 on 1,8 [2, 5] |
|||
.........Trying 7 on 3,8 [5, 7] |
|||
..........Trying 4 on 1,3 [1, 4] |
|||
...........Trying 9 on 1,1 [1, 9] |
|||
............Trying 1 on 3,1 [1, 2] |
|||
............Trying 2 on 3,1 [1, 2] |
|||
............Backtrack, path unsolvable... (on 3 1) |
|||
...........Trying 1 on 1,1 [1, 9] |
|||
...........Backtrack, path unsolvable... (on 1 1) |
|||
..........Trying 1 on 1,3 [1, 4] |
|||
...........Trying 9 on 1,1 [4, 9] |
|||
...........Trying 4 on 1,1 [4, 9] |
|||
...........Backtrack, path unsolvable... (on 1 1) |
|||
..........Backtrack, path unsolvable... (on 1 3) |
|||
.........Trying 5 on 3,8 [5, 7] |
|||
..........Trying 7 on 3,7 [1, 7] |
|||
...........Trying 2 on 2,1 [2, 4] |
|||
...........Trying 4 on 2,1 [2, 4] |
|||
...........Backtrack, path unsolvable... (on 2 1) |
|||
..........Trying 1 on 3,7 [1, 7] |
|||
..........Backtrack, path unsolvable... (on 3 7) |
|||
.........Backtrack, path unsolvable... (on 3 8) |
|||
........Backtrack, path unsolvable... (on 1 8) |
|||
.......Backtrack, path unsolvable... (on 7 9) |
|||
......Backtrack, path unsolvable... (on 8 9) |
|||
.....Trying 4 on 8,3 [3, 4] |
|||
......Trying 3 on 8,7 [2, 3] |
|||
.......Trying 6 on 8,9 [2, 6] |
|||
.......Trying 2 on 8,9 [2, 6] |
|||
.......Backtrack, path unsolvable... (on 8 9) |
|||
......Trying 2 on 8,7 [2, 3] |
|||
.......Trying 3 on 8,9 [3, 6] |
|||
.......Trying 6 on 8,9 [3, 6] |
|||
.......Backtrack, path unsolvable... (on 8 9) |
|||
......Backtrack, path unsolvable... (on 8 7) |
|||
.....Backtrack, path unsolvable... (on 8 3) |
|||
....Backtrack, path unsolvable... (on 8 1) |
|||
...Trying 3 on 9,8 [1, 3] |
|||
....Trying 4 on 8,1 [4, 5] |
|||
.....Trying 3 on 7,2 [3, 5] |
|||
.....Trying 5 on 7,2 [3, 5] |
|||
......Trying 6 on 7,9 [2, 6] |
|||
......Trying 2 on 7,9 [2, 6] |
|||
......Backtrack, path unsolvable... (on 7 9) |
|||
.....Backtrack, path unsolvable... (on 7 2) |
|||
....Trying 5 on 8,1 [4, 5] |
|||
.....Trying 6 on 8,9 [2, 6] |
|||
......Trying 8 on 1,9 [2, 8] |
|||
.......Trying 1 on 3,7 [1, 2] |
|||
.......Trying 2 on 3,7 [1, 2] |
|||
.......Backtrack, path unsolvable... (on 3 7) |
|||
......Trying 2 on 1,9 [2, 8] |
|||
.......Trying 7 on 3,8 [5, 7] |
|||
........Trying 5 on 3,7 [1, 5] |
|||
.........Trying 9 on 3,1 [1, 9] |
|||
.........Trying 1 on 3,1 [1, 9] |
|||
.........Backtrack, path unsolvable... (on 3 1) |
|||
........Trying 1 on 3,7 [1, 5] |
|||
.........Trying 9 on 3,1 [2, 9] |
|||
.........Trying 2 on 3,1 [2, 9] |
|||
.........Backtrack, path unsolvable... (on 3 1) |
|||
........Backtrack, path unsolvable... (on 3 7) |
|||
.......Trying 5 on 3,8 [5, 7] |
|||
........Trying 7 on 3,7 [1, 7] |
|||
.........Trying 9 on 3,1 [1, 9] |
|||
.........Trying 1 on 3,1 [1, 9] |
|||
.........Backtrack, path unsolvable... (on 3 1) |
|||
........Trying 1 on 3,7 [1, 7] |
|||
........Backtrack, path unsolvable... (on 3 7) |
|||
.......Backtrack, path unsolvable... (on 3 8) |
|||
......Backtrack, path unsolvable... (on 1 9) |
|||
.....Trying 2 on 8,9 [2, 6] |
|||
......Trying 5 on 1,8 [2, 5] |
|||
.......Trying 7 on 3,8 [2, 7] |
|||
........Trying 4 on 2,1 [1, 4] |
|||
........Trying 1 on 2,1 [1, 4] |
|||
........Backtrack, path unsolvable... (on 2 1) |
|||
.......Trying 2 on 3,8 [2, 7] |
|||
........Trying 9 on 3,1 [1, 9] |
|||
........Trying 1 on 3,1 [1, 9] |
|||
........Backtrack, path unsolvable... (on 3 1) |
|||
.......Backtrack, path unsolvable... (on 3 8) |
|||
......Trying 2 on 1,8 [2, 5] |
|||
.......Trying 7 on 3,8 [5, 7] |
|||
........Trying 1 on 3,7 [1, 5] |
|||
.........Trying 9 on 3,1 [2, 9] |
|||
.........Trying 2 on 3,1 [2, 9] |
|||
.........Backtrack, path unsolvable... (on 3 1) |
|||
........Trying 5 on 3,7 [1, 5] |
|||
.........Trying 9 on 3,1 [1, 9] |
|||
.........Trying 1 on 3,1 [1, 9] |
|||
.........Backtrack, path unsolvable... (on 3 1) |
|||
........Backtrack, path unsolvable... (on 3 7) |
|||
.......Trying 5 on 3,8 [5, 7] |
|||
........Trying 9 on 3,1 [1, 9] |
|||
........Trying 1 on 3,1 [1, 9] |
|||
........Backtrack, path unsolvable... (on 3 1) |
|||
.......Backtrack, path unsolvable... (on 3 8) |
|||
......Backtrack, path unsolvable... (on 1 8) |
|||
.....Backtrack, path unsolvable... (on 8 9) |
|||
....Backtrack, path unsolvable... (on 8 1) |
|||
...Backtrack, path unsolvable... (on 9 8) |
|||
..Trying 3 on 9,9 [3, 7] |
|||
...Trying 4 on 8,1 [4, 5] |
|||
....Trying 3 on 7,2 [3, 5] |
|||
....Trying 5 on 7,2 [3, 5] |
|||
.....Trying 6 on 7,9 [2, 6] |
|||
.....Trying 2 on 7,9 [2, 6] |
|||
.....Backtrack, path unsolvable... (on 7 9) |
|||
....Backtrack, path unsolvable... (on 7 2) |
|||
...Trying 5 on 8,1 [4, 5] |
|||
....Trying 6 on 8,9 [2, 6] |
|||
.....Trying 8 on 1,9 [2, 8] |
|||
......Trying 7 on 2,9 [2, 7] |
|||
.......Trying 1 on 3,7 [1, 2] |
|||
.......Trying 2 on 3,7 [1, 2] |
|||
.......Backtrack, path unsolvable... (on 3 7) |
|||
......Trying 2 on 2,9 [2, 7] |
|||
.......Trying 4 on 2,1 [1, 4] |
|||
.......Trying 1 on 2,1 [1, 4] |
|||
.......Backtrack, path unsolvable... (on 2 1) |
|||
......Backtrack, path unsolvable... (on 2 9) |
|||
.....Trying 2 on 1,9 [2, 8] |
|||
......Trying 3 on 3,8 [3, 5] |
|||
.......Trying 5 on 2,7 [1, 5] |
|||
........Trying 9 on 3,1 [2, 9] |
|||
........Trying 2 on 3,1 [2, 9] |
|||
........Backtrack, path unsolvable... (on 3 1) |
|||
.......Trying 1 on 2,7 [1, 5] |
|||
.......Backtrack, path unsolvable... (on 2 7) |
|||
......Trying 5 on 3,8 [3, 5] |
|||
.......Trying 3 on 3,7 [1, 3] |
|||
.......Trying 1 on 3,7 [1, 3] |
|||
.......Backtrack, path unsolvable... (on 3 7) |
|||
......Backtrack, path unsolvable... (on 3 8) |
|||
.....Backtrack, path unsolvable... (on 1 9) |
|||
....Trying 2 on 8,9 [2, 6] |
|||
.....Trying 5 on 1,8 [2, 5] |
|||
......Trying 3 on 3,8 [2, 3] |
|||
.......Trying 4 on 2,1 [1, 4] |
|||
.......Trying 1 on 2,1 [1, 4] |
|||
.......Backtrack, path unsolvable... (on 2 1) |
|||
......Trying 2 on 3,8 [2, 3] |
|||
.......Trying 9 on 3,1 [1, 9] |
|||
.......Trying 1 on 3,1 [1, 9] |
|||
.......Backtrack, path unsolvable... (on 3 1) |
|||
......Backtrack, path unsolvable... (on 3 8) |
|||
.....Trying 2 on 1,8 [2, 5] |
|||
......Trying 3 on 3,8 [3, 5] |
|||
.......Trying 4 on 1,3 [1, 4] |
|||
.......Trying 1 on 1,3 [1, 4] |
|||
.......Backtrack, path unsolvable... (on 1 3) |
|||
......Trying 5 on 3,8 [3, 5] |
|||
.......Trying 9 on 3,1 [1, 9] |
|||
.......Trying 1 on 3,1 [1, 9] |
|||
.......Backtrack, path unsolvable... (on 3 1) |
|||
......Backtrack, path unsolvable... (on 3 8) |
|||
.....Backtrack, path unsolvable... (on 1 8) |
|||
....Backtrack, path unsolvable... (on 8 9) |
|||
...Backtrack, path unsolvable... (on 8 1) |
|||
..Backtrack, path unsolvable... (on 9 9) |
|||
.Trying 3 on 9,2 [3, 6] |
|||
..Trying 7 on 9,9 [6, 7] |
|||
...Trying 1 on 9,8 [1, 6] |
|||
....Trying 4 on 8,1 [4, 5] |
|||
.....Trying 6 on 7,2 [5, 6] |
|||
......Trying 3 on 8,7 [2, 3] |
|||
.......Trying 6 on 8,9 [2, 6] |
|||
.......Trying 2 on 8,9 [2, 6] |
|||
.......Backtrack, path unsolvable... (on 8 9) |
|||
......Trying 2 on 8,7 [2, 3] |
|||
.......Trying 6 on 8,9 [3, 6] |
|||
.......Trying 3 on 8,9 [3, 6] |
|||
.......Backtrack, path unsolvable... (on 8 9) |
|||
......Backtrack, path unsolvable... (on 8 7) |
|||
.....Trying 5 on 7,2 [5, 6] |
|||
......Trying 4 on 1,2 [2, 4] |
|||
.......Trying 1 on 1,3 [1, 5] |
|||
........Trying 2 on 2,1 [2, 5] |
|||
........Trying 5 on 2,1 [2, 5] |
|||
........Backtrack, path unsolvable... (on 2 1) |
|||
.......Trying 5 on 1,3 [1, 5] |
|||
........Trying 1 on 2,1 [1, 2] |
|||
.........Trying 9 on 1,1 [2, 9] |
|||
..........Trying 8 on 1,9 [2, 8] |
|||
..........Trying 2 on 1,9 [2, 8] |
|||
..........Backtrack, path unsolvable... (on 1 9) |
|||
.........Trying 2 on 1,1 [2, 9] |
|||
.........Backtrack, path unsolvable... (on 1 1) |
|||
........Trying 2 on 2,1 [1, 2] |
|||
.........Trying 9 on 1,1 [1, 9] |
|||
..........Trying 8 on 1,9 [2, 8] |
|||
...........Trying 2 on 8,9 [2, 3] |
|||
...........Trying 3 on 8,9 [2, 3] |
|||
...........Backtrack, path unsolvable... (on 8 9) |
|||
..........Trying 2 on 1,9 [2, 8] |
|||
..........Backtrack, path unsolvable... (on 1 9) |
|||
.........Trying 1 on 1,1 [1, 9] |
|||
..........Trying 8 on 1,9 [2, 8] |
|||
...........Trying 2 on 8,9 [2, 3] |
|||
...........Trying 3 on 8,9 [2, 3] |
|||
...........Backtrack, path unsolvable... (on 8 9) |
|||
..........Trying 2 on 1,9 [2, 8] |
|||
..........Backtrack, path unsolvable... (on 1 9) |
|||
.........Backtrack, path unsolvable... (on 1 1) |
|||
........Backtrack, path unsolvable... (on 2 1) |
|||
.......Backtrack, path unsolvable... (on 1 3) |
|||
......Trying 2 on 1,2 [2, 4] |
|||
.......Trying 1 on 2,1 [1, 5] |
|||
........Trying 9 on 1,1 [5, 9] |
|||
.........Trying 8 on 1,9 [5, 8] |
|||
.........Trying 5 on 1,9 [5, 8] |
|||
.........Backtrack, path unsolvable... (on 1 9) |
|||
........Trying 5 on 1,1 [5, 9] |
|||
........Backtrack, path unsolvable... (on 1 1) |
|||
.......Trying 5 on 2,1 [1, 5] |
|||
........Trying 9 on 1,1 [1, 9] |
|||
.........Trying 8 on 1,9 [5, 8] |
|||
..........Trying 6 on 7,9 [3, 6] |
|||
..........Trying 3 on 7,9 [3, 6] |
|||
..........Backtrack, path unsolvable... (on 7 9) |
|||
.........Trying 5 on 1,9 [5, 8] |
|||
.........Backtrack, path unsolvable... (on 1 9) |
|||
........Trying 1 on 1,1 [1, 9] |
|||
.........Trying 8 on 1,9 [5, 8] |
|||
..........Trying 5 on 8,9 [3, 5] |
|||
..........Trying 3 on 8,9 [3, 5] |
|||
..........Backtrack, path unsolvable... (on 8 9) |
|||
.........Trying 5 on 1,9 [5, 8] |
|||
.........Backtrack, path unsolvable... (on 1 9) |
|||
........Backtrack, path unsolvable... (on 1 1) |
|||
.......Backtrack, path unsolvable... (on 2 1) |
|||
......Backtrack, path unsolvable... (on 1 2) |
|||
.....Backtrack, path unsolvable... (on 7 2) |
|||
....Trying 5 on 8,1 [4, 5] |
|||
.....Trying 6 on 8,3 [4, 6] |
|||
......Trying 3 on 8,9 [2, 3] |
|||
.......Trying 6 on 7,9 [5, 6] |
|||
........Trying 5 on 1,9 [2, 5] |
|||
.........Trying 3 on 3,8 [3, 7] |
|||
..........Trying 4 on 2,1 [1, 4] |
|||
..........Trying 1 on 2,1 [1, 4] |
|||
..........Backtrack, path unsolvable... (on 2 1) |
|||
.........Trying 7 on 3,8 [3, 7] |
|||
..........Trying 3 on 3,7 [1, 3] |
|||
..........Trying 1 on 3,7 [1, 3] |
|||
..........Backtrack, path unsolvable... (on 3 7) |
|||
.........Backtrack, path unsolvable... (on 3 8) |
|||
........Trying 2 on 1,9 [2, 5] |
|||
.........Trying 3 on 3,8 [3, 7] |
|||
..........Trying 7 on 2,7 [1, 7] |
|||
..........Trying 1 on 2,7 [1, 7] |
|||
...........Trying 4 on 2,1 [2, 4] |
|||
...........Trying 2 on 2,1 [2, 4] |
|||
...........Solved... (2 on 2,1) |
|||
..........Solved... (1 on 2,7) |
|||
.........Solved... (3 on 3,8) |
|||
........Solved... (2 on 1,9) |
|||
.......Solved... (6 on 7,9) |
|||
......Solved... (3 on 8,9) |
|||
.....Solved... (6 on 8,3) |
|||
....Solved... (5 on 8,1) |
|||
...Solved... (1 on 9,8) |
|||
..Solved... (7 on 9,9) |
|||
.Solved... (3 on 9,2) |
|||
Solved... (8 on 9,1) |
|||
--------------------------------------------- |
|||
9 5 4 1 3 7 6 8 2 |
|||
2 7 3 6 8 4 1 9 5 |
|||
1 6 8 2 9 5 7 3 4 |
|||
4 9 5 7 2 8 3 6 1 |
|||
6 8 1 4 5 3 2 7 9 |
|||
3 2 7 9 6 1 5 4 8 |
|||
7 4 9 3 1 2 8 5 6 |
|||
5 1 6 8 7 9 4 2 3 |
|||
8 3 2 5 4 6 9 1 7 |
|||
</pre> |
|||
=={{header|PHP}}== |
|||
{{trans|C++}} |
|||
<lang php> class SudokuSolver { |
|||
protected $grid = []; |
|||
protected $emptySymbol; |
|||
public static function parseString($str, $emptySymbol = '0') |
|||
{ |
|||
$grid = str_split($str); |
|||
foreach($grid as &$v) |
|||
{ |
|||
if($v == $emptySymbol) |
|||
{ |
|||
$v = 0; |
|||
} |
|||
else |
|||
{ |
|||
$v = (int)$v; |
|||
} |
|||
} |
|||
return $grid; |
|||
} |
|||
public function __construct($str, $emptySymbol = '0') { |
|||
if(strlen($str) !== 81) |
|||
{ |
|||
throw new \Exception('Error sudoku'); |
|||
} |
|||
$this->grid = static::parseString($str, $emptySymbol); |
|||
$this->emptySymbol = $emptySymbol; |
|||
} |
|||
public function solve() |
|||
{ |
|||
try |
|||
{ |
|||
$this->placeNumber(0); |
|||
return false; |
|||
} |
|||
catch(\Exception $e) |
|||
{ |
|||
return true; |
|||
} |
|||
} |
|||
protected function placeNumber($pos) |
|||
{ |
|||
if($pos == 81) |
|||
{ |
|||
throw new \Exception('Finish'); |
|||
} |
|||
if($this->grid[$pos] > 0) |
|||
{ |
|||
$this->placeNumber($pos+1); |
|||
return; |
|||
} |
|||
for($n = 1; $n <= 9; $n++) |
|||
{ |
|||
if($this->checkValidity($n, $pos%9, floor($pos/9))) |
|||
{ |
|||
$this->grid[$pos] = $n; |
|||
$this->placeNumber($pos+1); |
|||
$this->grid[$pos] = 0; |
|||
} |
|||
} |
|||
} |
|||
protected function checkValidity($val, $x, $y) |
|||
{ |
|||
for($i = 0; $i < 9; $i++) |
|||
{ |
|||
if(($this->grid[$y*9+$i] == $val) || ($this->grid[$i*9+$x] == $val)) |
|||
{ |
|||
return false; |
|||
} |
|||
} |
|||
$startX = (int) ((int)($x/3)*3); |
|||
$startY = (int) ((int)($y/3)*3); |
|||
for($i = $startY; $i<$startY+3;$i++) |
|||
{ |
|||
for($j = $startX; $j<$startX+3;$j++) |
|||
{ |
|||
if($this->grid[$i*9+$j] == $val) |
|||
{ |
|||
return false; |
|||
} |
|||
} |
|||
} |
|||
return true; |
|||
} |
|||
public function display() { |
|||
$str = ''; |
|||
for($i = 0; $i<9; $i++) |
|||
{ |
|||
for($j = 0; $j<9;$j++) |
|||
{ |
|||
$str .= $this->grid[$i*9+$j]; |
|||
$str .= " "; |
|||
if($j == 2 || $j == 5) |
|||
{ |
|||
$str .= "| "; |
|||
} |
|||
} |
|||
$str .= PHP_EOL; |
|||
if($i == 2 || $i == 5) |
|||
{ |
|||
$str .= "------+-------+------".PHP_EOL; |
|||
} |
|||
} |
|||
echo $str; |
|||
} |
|||
public function __toString() { |
|||
foreach ($this->grid as &$item) |
|||
{ |
|||
if($item == 0) |
|||
{ |
|||
$item = $this->emptySymbol; |
|||
} |
|||
} |
|||
return implode('', $this->grid); |
|||
} |
|||
} |
|||
$solver = new SudokuSolver('009170000020600001800200000200006053000051009005040080040000700006000320700003900'); |
|||
$solver->solve(); |
|||
$solver->display();</lang> |
|||
{{out}} |
|||
<pre> |
|||
3 6 9 | 1 7 5 | 8 4 2 |
|||
4 2 7 | 6 8 9 | 5 3 1 |
|||
8 5 1 | 2 3 4 | 6 9 7 |
|||
------+-------+------ |
|||
2 1 8 | 7 9 6 | 4 5 3 |
|||
6 3 4 | 8 5 1 | 2 7 9 |
|||
9 7 5 | 3 4 2 | 1 8 6 |
|||
------+-------+------ |
|||
1 4 3 | 9 2 8 | 7 6 5 |
|||
5 9 6 | 4 1 7 | 3 2 8 |
|||
7 8 2 | 5 6 3 | 9 1 4 |
|||
(solved in 0.027s) |
|||
</pre> |
</pre> |
||
Line 8,866: | Line 8,036: | ||
8 6 3 | 7 4 5 | 2 1 9 |
8 6 3 | 7 4 5 | 2 1 9 |
||
(logic), 0.02s |
(logic), 0.02s |
||
</pre> |
|||
=={{header|PHP}}== |
|||
{{trans|C++}} |
|||
<lang php> class SudokuSolver { |
|||
protected $grid = []; |
|||
protected $emptySymbol; |
|||
public static function parseString($str, $emptySymbol = '0') |
|||
{ |
|||
$grid = str_split($str); |
|||
foreach($grid as &$v) |
|||
{ |
|||
if($v == $emptySymbol) |
|||
{ |
|||
$v = 0; |
|||
} |
|||
else |
|||
{ |
|||
$v = (int)$v; |
|||
} |
|||
} |
|||
return $grid; |
|||
} |
|||
public function __construct($str, $emptySymbol = '0') { |
|||
if(strlen($str) !== 81) |
|||
{ |
|||
throw new \Exception('Error sudoku'); |
|||
} |
|||
$this->grid = static::parseString($str, $emptySymbol); |
|||
$this->emptySymbol = $emptySymbol; |
|||
} |
|||
public function solve() |
|||
{ |
|||
try |
|||
{ |
|||
$this->placeNumber(0); |
|||
return false; |
|||
} |
|||
catch(\Exception $e) |
|||
{ |
|||
return true; |
|||
} |
|||
} |
|||
protected function placeNumber($pos) |
|||
{ |
|||
if($pos == 81) |
|||
{ |
|||
throw new \Exception('Finish'); |
|||
} |
|||
if($this->grid[$pos] > 0) |
|||
{ |
|||
$this->placeNumber($pos+1); |
|||
return; |
|||
} |
|||
for($n = 1; $n <= 9; $n++) |
|||
{ |
|||
if($this->checkValidity($n, $pos%9, floor($pos/9))) |
|||
{ |
|||
$this->grid[$pos] = $n; |
|||
$this->placeNumber($pos+1); |
|||
$this->grid[$pos] = 0; |
|||
} |
|||
} |
|||
} |
|||
protected function checkValidity($val, $x, $y) |
|||
{ |
|||
for($i = 0; $i < 9; $i++) |
|||
{ |
|||
if(($this->grid[$y*9+$i] == $val) || ($this->grid[$i*9+$x] == $val)) |
|||
{ |
|||
return false; |
|||
} |
|||
} |
|||
$startX = (int) ((int)($x/3)*3); |
|||
$startY = (int) ((int)($y/3)*3); |
|||
for($i = $startY; $i<$startY+3;$i++) |
|||
{ |
|||
for($j = $startX; $j<$startX+3;$j++) |
|||
{ |
|||
if($this->grid[$i*9+$j] == $val) |
|||
{ |
|||
return false; |
|||
} |
|||
} |
|||
} |
|||
return true; |
|||
} |
|||
public function display() { |
|||
$str = ''; |
|||
for($i = 0; $i<9; $i++) |
|||
{ |
|||
for($j = 0; $j<9;$j++) |
|||
{ |
|||
$str .= $this->grid[$i*9+$j]; |
|||
$str .= " "; |
|||
if($j == 2 || $j == 5) |
|||
{ |
|||
$str .= "| "; |
|||
} |
|||
} |
|||
$str .= PHP_EOL; |
|||
if($i == 2 || $i == 5) |
|||
{ |
|||
$str .= "------+-------+------".PHP_EOL; |
|||
} |
|||
} |
|||
echo $str; |
|||
} |
|||
public function __toString() { |
|||
foreach ($this->grid as &$item) |
|||
{ |
|||
if($item == 0) |
|||
{ |
|||
$item = $this->emptySymbol; |
|||
} |
|||
} |
|||
return implode('', $this->grid); |
|||
} |
|||
} |
|||
$solver = new SudokuSolver('009170000020600001800200000200006053000051009005040080040000700006000320700003900'); |
|||
$solver->solve(); |
|||
$solver->display();</lang> |
|||
{{out}} |
|||
<pre> |
|||
3 6 9 | 1 7 5 | 8 4 2 |
|||
4 2 7 | 6 8 9 | 5 3 1 |
|||
8 5 1 | 2 3 4 | 6 9 7 |
|||
------+-------+------ |
|||
2 1 8 | 7 9 6 | 4 5 3 |
|||
6 3 4 | 8 5 1 | 2 7 9 |
|||
9 7 5 | 3 4 2 | 1 8 6 |
|||
------+-------+------ |
|||
1 4 3 | 9 2 8 | 7 6 5 |
|||
5 9 6 | 4 1 7 | 3 2 8 |
|||
7 8 2 | 5 6 3 | 9 1 4 |
|||
(solved in 0.027s) |
|||
</pre> |
</pre> |
||
Line 9,585: | Line 8,898: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
A [http://schemecookbook.org/view/Cookbook/SudokuSolver Sudoku Solver in Racket]. |
A [http://schemecookbook.org/view/Cookbook/SudokuSolver Sudoku Solver in Racket]. |
||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{trans|Perl}} |
|||
<lang perl6>use v6; |
|||
my @A = < |
|||
5 3 0 0 2 4 7 0 0 |
|||
0 0 2 0 0 0 8 0 0 |
|||
1 0 0 7 0 3 9 0 2 |
|||
0 0 8 0 7 2 0 4 9 |
|||
0 2 0 9 8 0 0 7 0 |
|||
7 9 0 0 0 0 0 8 0 |
|||
0 0 0 0 3 0 5 0 6 |
|||
9 6 0 0 1 0 3 0 0 |
|||
0 5 0 6 9 0 0 1 0 |
|||
>; |
|||
my &I = * div 9; # line number |
|||
my &J = * % 9; # column number |
|||
my &K = { ($_ div 27) * 3 + $_ % 9 div 3 }; # bloc number |
|||
sub solve { |
|||
for ^@A -> $i { |
|||
next if @A[$i]; |
|||
my @taken-values = @A[ |
|||
grep { |
|||
I($_) == I($i) || J($_) == J($i) || K($_) == K($i) |
|||
}, ^@A |
|||
]; |
|||
for grep none(@taken-values), 1..9 { |
|||
@A[$i] = $_; |
|||
solve; |
|||
} |
|||
return @A[$i] = 0; |
|||
} |
|||
my $i = 1; |
|||
for ^@A { |
|||
print "@A[$_] "; |
|||
print " " if $i %% 3; |
|||
print "\n" if $i %% 9; |
|||
print "\n" if $i++ %% 27; |
|||
} |
|||
} |
|||
solve;</lang> |
|||
{{out}} |
|||
<pre>5 3 9 8 2 4 7 6 1 |
|||
6 7 2 1 5 9 8 3 4 |
|||
1 8 4 7 6 3 9 5 2 |
|||
3 1 8 5 7 2 6 4 9 |
|||
4 2 5 9 8 6 1 7 3 |
|||
7 9 6 3 4 1 2 8 5 |
|||
8 4 1 2 3 7 5 9 6 |
|||
9 6 7 4 1 5 3 2 8 |
|||
2 5 3 6 9 8 4 1 7</pre> |
|||
This is an alternative solution that uses a more ellaborate set of choices instead of brute-forcing it. |
|||
<lang perl6>#!/usr/bin/env perl6 |
|||
use v6; |
|||
# |
|||
# In this code, a sudoku puzzle is represented as a two-dimentional |
|||
# array. The cells that are not yet solved are represented by yet |
|||
# another array of all the possible values. |
|||
# |
|||
# This implementation is not a simple brute force evaluation of all |
|||
# the options, but rather makes four extra attempts to guide the |
|||
# solution: |
|||
# |
|||
# 1) For every change in the grid, usually made by an attempt at a |
|||
# solution, we will reduce the search space of the possible values |
|||
# in all the other cells before going forward. |
|||
# |
|||
# 2) When a cell that is not yet resolved is the only one that can |
|||
# hold a specific value, resolve it immediately instead of |
|||
# performing the regular search. |
|||
# |
|||
# 3) Instead of trying from cell 1,1 and moving in sequence, this |
|||
# implementation will start trying on the cell that is the closest |
|||
# to being solved already. |
|||
# |
|||
# 4) Instead of trying all possible values in sequence, start with |
|||
# the value that is the most unique. I.e.: If the options for this |
|||
# cell are 1,4,6 and 6 is only a candidate for two of the |
|||
# competing cells, we start with that one. |
|||
# |
|||
# keep a list with all the cells, handy for traversal |
|||
my @cells = do for (flat 0..8 X 0..8) -> $x, $y { [ $x, $y ] }; |
|||
# |
|||
# Try to solve this puzzle and return the resolved puzzle if it is at |
|||
# all solvable in this configuration. |
|||
sub solve($sudoku, Int $level) { |
|||
# cleanup the impossible values first, |
|||
if (cleanup-impossible-values($sudoku, $level)) { |
|||
# try to find implicit answers |
|||
while (find-implicit-answers($sudoku, $level)) { |
|||
# and every time you find some, re-do the cleanup and try again |
|||
cleanup-impossible-values($sudoku, $level); |
|||
} |
|||
# Now let's actually try to solve a new value. But instead of |
|||
# going in sequence, we select the cell that is the closest to |
|||
# being solved already. This will reduce the overall number of |
|||
# guesses. |
|||
for sort { solution-complexity-factor($sudoku, $_[0], $_[1]) }, |
|||
grep { $sudoku[$_[0]][$_[1]] ~~ Array }, |
|||
@cells -> $cell |
|||
{ |
|||
my Int ($x, $y) = @($cell); |
|||
# Now let's try the possible values in the order of |
|||
# uniqueness. |
|||
for sort { matches-in-competing-cells($sudoku, $x, $y, $_) }, @($sudoku[$x][$y]) -> $val { |
|||
trace $level, "Trying $val on "~($x+1)~","~($y+1)~" "~$sudoku[$x][$y].perl; |
|||
my $solution = clone-sudoku($sudoku); |
|||
$solution[$x][$y] = $val; |
|||
my $solved = solve($solution, $level+1); |
|||
if $solved { |
|||
trace $level, "Solved... ($val on "~($x+1)~","~($y+1)~")"; |
|||
return $solved; |
|||
} |
|||
} |
|||
# if we fell through, it means that we found no valid |
|||
# value for this cell |
|||
trace $level, "Backtrack, path unsolvable... (on "~($x+1)~" "~($y+1)~")"; |
|||
return 0; |
|||
} |
|||
# all cells are already solved. |
|||
return $sudoku; |
|||
} else { |
|||
# if the cleanup failed, it means this is an invalid grid. |
|||
return False; |
|||
} |
|||
} |
|||
# This function reduces the search space from values that are already |
|||
# assigned to competing cells. |
|||
sub cleanup-impossible-values($sudoku, Int $level = 1) { |
|||
my Bool $resolved; |
|||
repeat { |
|||
$resolved = False; |
|||
for grep { $sudoku[$_[0]][$_[1]] ~~ Array }, |
|||
@cells -> $cell { |
|||
my Int ($x, $y) = @($cell); |
|||
# which block is this cell in |
|||
my Int $bx = Int($x / 3); |
|||
my Int $by = Int($y / 3); |
|||
# A unfilled cell is not resolved, so it shouldn't match |
|||
my multi match-resolved-cell(Array $other, Int $this) { |
|||
return 0; |
|||
} |
|||
my multi match-resolved-cell(Int $other, Int $this) { |
|||
return $other == $this; |
|||
} |
|||
# Reduce the possible values to the ones that are still |
|||
# valid |
|||
my @r = |
|||
grep { !match-resolved-cell($sudoku[any(0..2)+3*$bx][any(0..2)+3*$by], $_) }, # same block |
|||
grep { !match-resolved-cell($sudoku[any(0..8)][$y], $_) }, # same line |
|||
grep { !match-resolved-cell($sudoku[$x][any(0..8)], $_) }, # same column |
|||
@($sudoku[$x][$y]); |
|||
if (@r.elems == 1) { |
|||
# if only one element is left, then make it resolved |
|||
$sudoku[$x][$y] = @r[0]; |
|||
$resolved = True; |
|||
} elsif (@r.elems == 0) { |
|||
# This is an invalid grid |
|||
return 0; |
|||
} else { |
|||
$sudoku[$x][$y] = @r; |
|||
} |
|||
} |
|||
} while $resolved; # repeat if there was any change |
|||
return 1; |
|||
} |
|||
sub solution-complexity-factor($sudoku, Int $x, Int $y) { |
|||
my Int $bx = Int($x / 3); # this block |
|||
my Int $by = Int($y / 3); |
|||
my multi count-values(Array $val) { |
|||
return $val.elems; |
|||
} |
|||
my multi count-values(Int $val) { |
|||
return 1; |
|||
} |
|||
# the number of possible values should take precedence |
|||
my Int $f = 1000 * count-values($sudoku[$x][$y]); |
|||
for (flat 0..2 X 0..2) -> $lx, $ly { |
|||
$f += count-values($sudoku[$lx+$bx*3][$ly+$by*3]) |
|||
} |
|||
for 0..^($by*3), (($by+1)*3)..8 -> $ly { |
|||
$f += count-values($sudoku[$x][$ly]) |
|||
} |
|||
for 0..^($bx*3), (($bx+1)*3)..8 -> $lx { |
|||
$f += count-values($sudoku[$lx][$y]) |
|||
} |
|||
return $f; |
|||
} |
|||
sub matches-in-competing-cells($sudoku, Int $x, Int $y, Int $val) { |
|||
my Int $bx = Int($x / 3); # this block |
|||
my Int $by = Int($y / 3); |
|||
# Function to decide which possible value to try first |
|||
my multi cell-matching(Int $cell) { |
|||
return $val == $cell ?? 1 !! 0; |
|||
} |
|||
my multi cell-matching(Array $cell) { |
|||
return $cell.grep({ $val == $_ }) ?? 1 !! 0; |
|||
} |
|||
my Int $c = 0; |
|||
for (flat 0..2 X 0..2) -> $lx, $ly { |
|||
$c += cell-matching($sudoku[$lx+$bx*3][$ly+$by*3]) |
|||
} |
|||
for 0..^($by*3), (($by+1)*3)..8 -> $ly { |
|||
$c += cell-matching($sudoku[$x][$ly]) |
|||
} |
|||
for 0..^($bx*3), (($bx+1)*3)..8 -> $lx { |
|||
$c += cell-matching($sudoku[$lx][$y]) |
|||
} |
|||
return $c; |
|||
} |
|||
sub find-implicit-answers($sudoku, Int $level) { |
|||
my Bool $resolved = False; |
|||
for grep { $sudoku[$_[0]][$_[1]] ~~ Array }, |
|||
@cells -> $cell { |
|||
my Int ($x, $y) = @($cell); |
|||
for @($sudoku[$x][$y]) -> $val { |
|||
# If this is the only cell with this val as a possibility, |
|||
# just make it resolved already |
|||
if (matches-in-competing-cells($sudoku, $x, $y, $val) == 1) { |
|||
$sudoku[$x][$y] = $val; |
|||
$resolved = True; |
|||
} |
|||
} |
|||
} |
|||
return $resolved; |
|||
} |
|||
my $puzzle = |
|||
map { [ map { $_ == 0 ?? [1..9] !! $_+0 }, @($_) ] }, |
|||
[ 0,0,0,0,3,7,6,0,0 ], |
|||
[ 0,0,0,6,0,0,0,9,0 ], |
|||
[ 0,0,8,0,0,0,0,0,4 ], |
|||
[ 0,9,0,0,0,0,0,0,1 ], |
|||
[ 6,0,0,0,0,0,0,0,9 ], |
|||
[ 3,0,0,0,0,0,0,4,0 ], |
|||
[ 7,0,0,0,0,0,8,0,0 ], |
|||
[ 0,1,0,0,0,9,0,0,0 ], |
|||
[ 0,0,2,5,4,0,0,0,0 ]; |
|||
my $solved = solve($puzzle, 0); |
|||
if $solved { |
|||
print-sudoku($solved,0); |
|||
} else { |
|||
say "unsolvable."; |
|||
} |
|||
# Utility functions, not really part of the solution |
|||
sub trace(Int $level, Str $message) { |
|||
say '.' x $level, $message; |
|||
} |
|||
sub clone-sudoku($sudoku) { |
|||
my $clone; |
|||
for (flat 0..8 X 0..8) -> $x, $y { |
|||
$clone[$x][$y] = $sudoku[$x][$y]; |
|||
} |
|||
return $clone; |
|||
} |
|||
sub print-sudoku($sudoku, Int $level = 1) { |
|||
trace $level, '-' x 5*9; |
|||
for @($sudoku) -> $row { |
|||
trace $level, join " ", do for @($row) -> $cell { |
|||
$cell ~~ Array ?? "#{$cell.elems}#" !! " $cell " |
|||
} |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
Trying 8 on 9,1 [8, 9] |
|||
.Trying 6 on 9,2 [3, 6] |
|||
..Trying 7 on 9,9 [3, 7] |
|||
...Trying 1 on 9,8 [1, 3] |
|||
....Trying 4 on 8,1 [4, 5] |
|||
.....Trying 3 on 7,2 [3, 5] |
|||
......Trying 3 on 8,7 [2, 3] |
|||
.......Trying 6 on 8,9 [2, 6] |
|||
.......Trying 2 on 8,9 [2, 6] |
|||
.......Backtrack, path unsolvable... (on 8 9) |
|||
......Trying 2 on 8,7 [2, 3] |
|||
.......Trying 3 on 8,9 [3, 6] |
|||
.......Trying 6 on 8,9 [3, 6] |
|||
.......Backtrack, path unsolvable... (on 8 9) |
|||
......Backtrack, path unsolvable... (on 8 7) |
|||
.....Trying 5 on 7,2 [3, 5] |
|||
......Trying 5 on 8,7 [2, 5] |
|||
.......Trying 6 on 8,9 [2, 6] |
|||
.......Trying 2 on 8,9 [2, 6] |
|||
.......Backtrack, path unsolvable... (on 8 9) |
|||
......Trying 2 on 8,7 [2, 5] |
|||
.......Trying 5 on 8,9 [5, 6] |
|||
.......Trying 6 on 8,9 [5, 6] |
|||
.......Backtrack, path unsolvable... (on 8 9) |
|||
......Backtrack, path unsolvable... (on 8 7) |
|||
.....Backtrack, path unsolvable... (on 7 2) |
|||
....Trying 5 on 8,1 [4, 5] |
|||
.....Trying 3 on 8,3 [3, 4] |
|||
......Trying 6 on 8,9 [2, 6] |
|||
.......Trying 3 on 7,9 [3, 5] |
|||
........Trying 5 on 1,9 [2, 5] |
|||
.........Trying 3 on 3,8 [3, 7] |
|||
..........Trying 4 on 2,1 [1, 4] |
|||
..........Trying 1 on 2,1 [1, 4] |
|||
..........Backtrack, path unsolvable... (on 2 1) |
|||
.........Trying 7 on 3,8 [3, 7] |
|||
..........Trying 3 on 3,7 [1, 3] |
|||
..........Trying 1 on 3,7 [1, 3] |
|||
..........Backtrack, path unsolvable... (on 3 7) |
|||
.........Backtrack, path unsolvable... (on 3 8) |
|||
........Trying 2 on 1,9 [2, 5] |
|||
.........Trying 3 on 3,8 [3, 7] |
|||
..........Trying 7 on 2,7 [1, 7] |
|||
...........Trying 9 on 3,1 [2, 9] |
|||
...........Trying 2 on 3,1 [2, 9] |
|||
...........Backtrack, path unsolvable... (on 3 1) |
|||
..........Trying 1 on 2,7 [1, 7] |
|||
..........Backtrack, path unsolvable... (on 2 7) |
|||
.........Trying 7 on 3,8 [3, 7] |
|||
..........Trying 3 on 3,7 [1, 3] |
|||
..........Trying 1 on 3,7 [1, 3] |
|||
...........Trying 9 on 3,1 [2, 9] |
|||
...........Trying 2 on 3,1 [2, 9] |
|||
...........Backtrack, path unsolvable... (on 3 1) |
|||
..........Backtrack, path unsolvable... (on 3 7) |
|||
.........Backtrack, path unsolvable... (on 3 8) |
|||
........Backtrack, path unsolvable... (on 1 9) |
|||
.......Trying 5 on 7,9 [3, 5] |
|||
........Trying 8 on 1,9 [2, 8] |
|||
.........Trying 2 on 3,7 [1, 2] |
|||
.........Trying 1 on 3,7 [1, 2] |
|||
.........Backtrack, path unsolvable... (on 3 7) |
|||
........Trying 2 on 1,9 [2, 8] |
|||
.........Trying 7 on 3,8 [5, 7] |
|||
..........Trying 5 on 3,7 [1, 5] |
|||
...........Trying 2 on 2,1 [2, 4] |
|||
...........Trying 4 on 2,1 [2, 4] |
|||
...........Backtrack, path unsolvable... (on 2 1) |
|||
..........Trying 1 on 3,7 [1, 5] |
|||
...........Trying 9 on 3,1 [2, 9] |
|||
...........Trying 2 on 3,1 [2, 9] |
|||
...........Backtrack, path unsolvable... (on 3 1) |
|||
..........Backtrack, path unsolvable... (on 3 7) |
|||
.........Trying 5 on 3,8 [5, 7] |
|||
..........Trying 7 on 3,7 [1, 7] |
|||
...........Trying 2 on 2,1 [2, 4] |
|||
...........Trying 4 on 2,1 [2, 4] |
|||
...........Backtrack, path unsolvable... (on 2 1) |
|||
..........Trying 1 on 3,7 [1, 7] |
|||
..........Backtrack, path unsolvable... (on 3 7) |
|||
.........Backtrack, path unsolvable... (on 3 8) |
|||
........Backtrack, path unsolvable... (on 1 9) |
|||
.......Backtrack, path unsolvable... (on 7 9) |
|||
......Trying 2 on 8,9 [2, 6] |
|||
.......Trying 3 on 7,9 [3, 5] |
|||
........Trying 8 on 1,9 [5, 8] |
|||
.........Trying 3 on 3,8 [3, 7] |
|||
..........Trying 4 on 1,3 [1, 4] |
|||
...........Trying 9 on 1,1 [1, 9] |
|||
............Trying 1 on 3,1 [1, 2] |
|||
............Trying 2 on 3,1 [1, 2] |
|||
............Backtrack, path unsolvable... (on 3 1) |
|||
...........Trying 1 on 1,1 [1, 9] |
|||
...........Backtrack, path unsolvable... (on 1 1) |
|||
..........Trying 1 on 1,3 [1, 4] |
|||
...........Trying 9 on 1,1 [4, 9] |
|||
...........Trying 4 on 1,1 [4, 9] |
|||
...........Backtrack, path unsolvable... (on 1 1) |
|||
..........Backtrack, path unsolvable... (on 1 3) |
|||
.........Trying 7 on 3,8 [3, 7] |
|||
..........Trying 3 on 3,7 [1, 3] |
|||
..........Trying 1 on 3,7 [1, 3] |
|||
...........Trying 9 on 3,1 [2, 9] |
|||
...........Trying 2 on 3,1 [2, 9] |
|||
...........Backtrack, path unsolvable... (on 3 1) |
|||
..........Backtrack, path unsolvable... (on 3 7) |
|||
.........Backtrack, path unsolvable... (on 3 8) |
|||
........Trying 5 on 1,9 [5, 8] |
|||
........Backtrack, path unsolvable... (on 1 9) |
|||
.......Trying 5 on 7,9 [3, 5] |
|||
........Trying 5 on 1,8 [2, 5] |
|||
.........Trying 7 on 3,8 [2, 7] |
|||
..........Trying 4 on 1,3 [1, 4] |
|||
..........Trying 1 on 1,3 [1, 4] |
|||
..........Backtrack, path unsolvable... (on 1 3) |
|||
.........Trying 2 on 3,8 [2, 7] |
|||
..........Trying 9 on 3,1 [1, 9] |
|||
..........Trying 1 on 3,1 [1, 9] |
|||
..........Backtrack, path unsolvable... (on 3 1) |
|||
.........Backtrack, path unsolvable... (on 3 8) |
|||
........Trying 2 on 1,8 [2, 5] |
|||
.........Trying 7 on 3,8 [5, 7] |
|||
..........Trying 4 on 1,3 [1, 4] |
|||
...........Trying 9 on 1,1 [1, 9] |
|||
............Trying 1 on 3,1 [1, 2] |
|||
............Trying 2 on 3,1 [1, 2] |
|||
............Backtrack, path unsolvable... (on 3 1) |
|||
...........Trying 1 on 1,1 [1, 9] |
|||
...........Backtrack, path unsolvable... (on 1 1) |
|||
..........Trying 1 on 1,3 [1, 4] |
|||
...........Trying 9 on 1,1 [4, 9] |
|||
...........Trying 4 on 1,1 [4, 9] |
|||
...........Backtrack, path unsolvable... (on 1 1) |
|||
..........Backtrack, path unsolvable... (on 1 3) |
|||
.........Trying 5 on 3,8 [5, 7] |
|||
..........Trying 7 on 3,7 [1, 7] |
|||
...........Trying 2 on 2,1 [2, 4] |
|||
...........Trying 4 on 2,1 [2, 4] |
|||
...........Backtrack, path unsolvable... (on 2 1) |
|||
..........Trying 1 on 3,7 [1, 7] |
|||
..........Backtrack, path unsolvable... (on 3 7) |
|||
.........Backtrack, path unsolvable... (on 3 8) |
|||
........Backtrack, path unsolvable... (on 1 8) |
|||
.......Backtrack, path unsolvable... (on 7 9) |
|||
......Backtrack, path unsolvable... (on 8 9) |
|||
.....Trying 4 on 8,3 [3, 4] |
|||
......Trying 3 on 8,7 [2, 3] |
|||
.......Trying 6 on 8,9 [2, 6] |
|||
.......Trying 2 on 8,9 [2, 6] |
|||
.......Backtrack, path unsolvable... (on 8 9) |
|||
......Trying 2 on 8,7 [2, 3] |
|||
.......Trying 3 on 8,9 [3, 6] |
|||
.......Trying 6 on 8,9 [3, 6] |
|||
.......Backtrack, path unsolvable... (on 8 9) |
|||
......Backtrack, path unsolvable... (on 8 7) |
|||
.....Backtrack, path unsolvable... (on 8 3) |
|||
....Backtrack, path unsolvable... (on 8 1) |
|||
...Trying 3 on 9,8 [1, 3] |
|||
....Trying 4 on 8,1 [4, 5] |
|||
.....Trying 3 on 7,2 [3, 5] |
|||
.....Trying 5 on 7,2 [3, 5] |
|||
......Trying 6 on 7,9 [2, 6] |
|||
......Trying 2 on 7,9 [2, 6] |
|||
......Backtrack, path unsolvable... (on 7 9) |
|||
.....Backtrack, path unsolvable... (on 7 2) |
|||
....Trying 5 on 8,1 [4, 5] |
|||
.....Trying 6 on 8,9 [2, 6] |
|||
......Trying 8 on 1,9 [2, 8] |
|||
.......Trying 1 on 3,7 [1, 2] |
|||
.......Trying 2 on 3,7 [1, 2] |
|||
.......Backtrack, path unsolvable... (on 3 7) |
|||
......Trying 2 on 1,9 [2, 8] |
|||
.......Trying 7 on 3,8 [5, 7] |
|||
........Trying 5 on 3,7 [1, 5] |
|||
.........Trying 9 on 3,1 [1, 9] |
|||
.........Trying 1 on 3,1 [1, 9] |
|||
.........Backtrack, path unsolvable... (on 3 1) |
|||
........Trying 1 on 3,7 [1, 5] |
|||
.........Trying 9 on 3,1 [2, 9] |
|||
.........Trying 2 on 3,1 [2, 9] |
|||
.........Backtrack, path unsolvable... (on 3 1) |
|||
........Backtrack, path unsolvable... (on 3 7) |
|||
.......Trying 5 on 3,8 [5, 7] |
|||
........Trying 7 on 3,7 [1, 7] |
|||
.........Trying 9 on 3,1 [1, 9] |
|||
.........Trying 1 on 3,1 [1, 9] |
|||
.........Backtrack, path unsolvable... (on 3 1) |
|||
........Trying 1 on 3,7 [1, 7] |
|||
........Backtrack, path unsolvable... (on 3 7) |
|||
.......Backtrack, path unsolvable... (on 3 8) |
|||
......Backtrack, path unsolvable... (on 1 9) |
|||
.....Trying 2 on 8,9 [2, 6] |
|||
......Trying 5 on 1,8 [2, 5] |
|||
.......Trying 7 on 3,8 [2, 7] |
|||
........Trying 4 on 2,1 [1, 4] |
|||
........Trying 1 on 2,1 [1, 4] |
|||
........Backtrack, path unsolvable... (on 2 1) |
|||
.......Trying 2 on 3,8 [2, 7] |
|||
........Trying 9 on 3,1 [1, 9] |
|||
........Trying 1 on 3,1 [1, 9] |
|||
........Backtrack, path unsolvable... (on 3 1) |
|||
.......Backtrack, path unsolvable... (on 3 8) |
|||
......Trying 2 on 1,8 [2, 5] |
|||
.......Trying 7 on 3,8 [5, 7] |
|||
........Trying 1 on 3,7 [1, 5] |
|||
.........Trying 9 on 3,1 [2, 9] |
|||
.........Trying 2 on 3,1 [2, 9] |
|||
.........Backtrack, path unsolvable... (on 3 1) |
|||
........Trying 5 on 3,7 [1, 5] |
|||
.........Trying 9 on 3,1 [1, 9] |
|||
.........Trying 1 on 3,1 [1, 9] |
|||
.........Backtrack, path unsolvable... (on 3 1) |
|||
........Backtrack, path unsolvable... (on 3 7) |
|||
.......Trying 5 on 3,8 [5, 7] |
|||
........Trying 9 on 3,1 [1, 9] |
|||
........Trying 1 on 3,1 [1, 9] |
|||
........Backtrack, path unsolvable... (on 3 1) |
|||
.......Backtrack, path unsolvable... (on 3 8) |
|||
......Backtrack, path unsolvable... (on 1 8) |
|||
.....Backtrack, path unsolvable... (on 8 9) |
|||
....Backtrack, path unsolvable... (on 8 1) |
|||
...Backtrack, path unsolvable... (on 9 8) |
|||
..Trying 3 on 9,9 [3, 7] |
|||
...Trying 4 on 8,1 [4, 5] |
|||
....Trying 3 on 7,2 [3, 5] |
|||
....Trying 5 on 7,2 [3, 5] |
|||
.....Trying 6 on 7,9 [2, 6] |
|||
.....Trying 2 on 7,9 [2, 6] |
|||
.....Backtrack, path unsolvable... (on 7 9) |
|||
....Backtrack, path unsolvable... (on 7 2) |
|||
...Trying 5 on 8,1 [4, 5] |
|||
....Trying 6 on 8,9 [2, 6] |
|||
.....Trying 8 on 1,9 [2, 8] |
|||
......Trying 7 on 2,9 [2, 7] |
|||
.......Trying 1 on 3,7 [1, 2] |
|||
.......Trying 2 on 3,7 [1, 2] |
|||
.......Backtrack, path unsolvable... (on 3 7) |
|||
......Trying 2 on 2,9 [2, 7] |
|||
.......Trying 4 on 2,1 [1, 4] |
|||
.......Trying 1 on 2,1 [1, 4] |
|||
.......Backtrack, path unsolvable... (on 2 1) |
|||
......Backtrack, path unsolvable... (on 2 9) |
|||
.....Trying 2 on 1,9 [2, 8] |
|||
......Trying 3 on 3,8 [3, 5] |
|||
.......Trying 5 on 2,7 [1, 5] |
|||
........Trying 9 on 3,1 [2, 9] |
|||
........Trying 2 on 3,1 [2, 9] |
|||
........Backtrack, path unsolvable... (on 3 1) |
|||
.......Trying 1 on 2,7 [1, 5] |
|||
.......Backtrack, path unsolvable... (on 2 7) |
|||
......Trying 5 on 3,8 [3, 5] |
|||
.......Trying 3 on 3,7 [1, 3] |
|||
.......Trying 1 on 3,7 [1, 3] |
|||
.......Backtrack, path unsolvable... (on 3 7) |
|||
......Backtrack, path unsolvable... (on 3 8) |
|||
.....Backtrack, path unsolvable... (on 1 9) |
|||
....Trying 2 on 8,9 [2, 6] |
|||
.....Trying 5 on 1,8 [2, 5] |
|||
......Trying 3 on 3,8 [2, 3] |
|||
.......Trying 4 on 2,1 [1, 4] |
|||
.......Trying 1 on 2,1 [1, 4] |
|||
.......Backtrack, path unsolvable... (on 2 1) |
|||
......Trying 2 on 3,8 [2, 3] |
|||
.......Trying 9 on 3,1 [1, 9] |
|||
.......Trying 1 on 3,1 [1, 9] |
|||
.......Backtrack, path unsolvable... (on 3 1) |
|||
......Backtrack, path unsolvable... (on 3 8) |
|||
.....Trying 2 on 1,8 [2, 5] |
|||
......Trying 3 on 3,8 [3, 5] |
|||
.......Trying 4 on 1,3 [1, 4] |
|||
.......Trying 1 on 1,3 [1, 4] |
|||
.......Backtrack, path unsolvable... (on 1 3) |
|||
......Trying 5 on 3,8 [3, 5] |
|||
.......Trying 9 on 3,1 [1, 9] |
|||
.......Trying 1 on 3,1 [1, 9] |
|||
.......Backtrack, path unsolvable... (on 3 1) |
|||
......Backtrack, path unsolvable... (on 3 8) |
|||
.....Backtrack, path unsolvable... (on 1 8) |
|||
....Backtrack, path unsolvable... (on 8 9) |
|||
...Backtrack, path unsolvable... (on 8 1) |
|||
..Backtrack, path unsolvable... (on 9 9) |
|||
.Trying 3 on 9,2 [3, 6] |
|||
..Trying 7 on 9,9 [6, 7] |
|||
...Trying 1 on 9,8 [1, 6] |
|||
....Trying 4 on 8,1 [4, 5] |
|||
.....Trying 6 on 7,2 [5, 6] |
|||
......Trying 3 on 8,7 [2, 3] |
|||
.......Trying 6 on 8,9 [2, 6] |
|||
.......Trying 2 on 8,9 [2, 6] |
|||
.......Backtrack, path unsolvable... (on 8 9) |
|||
......Trying 2 on 8,7 [2, 3] |
|||
.......Trying 6 on 8,9 [3, 6] |
|||
.......Trying 3 on 8,9 [3, 6] |
|||
.......Backtrack, path unsolvable... (on 8 9) |
|||
......Backtrack, path unsolvable... (on 8 7) |
|||
.....Trying 5 on 7,2 [5, 6] |
|||
......Trying 4 on 1,2 [2, 4] |
|||
.......Trying 1 on 1,3 [1, 5] |
|||
........Trying 2 on 2,1 [2, 5] |
|||
........Trying 5 on 2,1 [2, 5] |
|||
........Backtrack, path unsolvable... (on 2 1) |
|||
.......Trying 5 on 1,3 [1, 5] |
|||
........Trying 1 on 2,1 [1, 2] |
|||
.........Trying 9 on 1,1 [2, 9] |
|||
..........Trying 8 on 1,9 [2, 8] |
|||
..........Trying 2 on 1,9 [2, 8] |
|||
..........Backtrack, path unsolvable... (on 1 9) |
|||
.........Trying 2 on 1,1 [2, 9] |
|||
.........Backtrack, path unsolvable... (on 1 1) |
|||
........Trying 2 on 2,1 [1, 2] |
|||
.........Trying 9 on 1,1 [1, 9] |
|||
..........Trying 8 on 1,9 [2, 8] |
|||
...........Trying 2 on 8,9 [2, 3] |
|||
...........Trying 3 on 8,9 [2, 3] |
|||
...........Backtrack, path unsolvable... (on 8 9) |
|||
..........Trying 2 on 1,9 [2, 8] |
|||
..........Backtrack, path unsolvable... (on 1 9) |
|||
.........Trying 1 on 1,1 [1, 9] |
|||
..........Trying 8 on 1,9 [2, 8] |
|||
...........Trying 2 on 8,9 [2, 3] |
|||
...........Trying 3 on 8,9 [2, 3] |
|||
...........Backtrack, path unsolvable... (on 8 9) |
|||
..........Trying 2 on 1,9 [2, 8] |
|||
..........Backtrack, path unsolvable... (on 1 9) |
|||
.........Backtrack, path unsolvable... (on 1 1) |
|||
........Backtrack, path unsolvable... (on 2 1) |
|||
.......Backtrack, path unsolvable... (on 1 3) |
|||
......Trying 2 on 1,2 [2, 4] |
|||
.......Trying 1 on 2,1 [1, 5] |
|||
........Trying 9 on 1,1 [5, 9] |
|||
.........Trying 8 on 1,9 [5, 8] |
|||
.........Trying 5 on 1,9 [5, 8] |
|||
.........Backtrack, path unsolvable... (on 1 9) |
|||
........Trying 5 on 1,1 [5, 9] |
|||
........Backtrack, path unsolvable... (on 1 1) |
|||
.......Trying 5 on 2,1 [1, 5] |
|||
........Trying 9 on 1,1 [1, 9] |
|||
.........Trying 8 on 1,9 [5, 8] |
|||
..........Trying 6 on 7,9 [3, 6] |
|||
..........Trying 3 on 7,9 [3, 6] |
|||
..........Backtrack, path unsolvable... (on 7 9) |
|||
.........Trying 5 on 1,9 [5, 8] |
|||
.........Backtrack, path unsolvable... (on 1 9) |
|||
........Trying 1 on 1,1 [1, 9] |
|||
.........Trying 8 on 1,9 [5, 8] |
|||
..........Trying 5 on 8,9 [3, 5] |
|||
..........Trying 3 on 8,9 [3, 5] |
|||
..........Backtrack, path unsolvable... (on 8 9) |
|||
.........Trying 5 on 1,9 [5, 8] |
|||
.........Backtrack, path unsolvable... (on 1 9) |
|||
........Backtrack, path unsolvable... (on 1 1) |
|||
.......Backtrack, path unsolvable... (on 2 1) |
|||
......Backtrack, path unsolvable... (on 1 2) |
|||
.....Backtrack, path unsolvable... (on 7 2) |
|||
....Trying 5 on 8,1 [4, 5] |
|||
.....Trying 6 on 8,3 [4, 6] |
|||
......Trying 3 on 8,9 [2, 3] |
|||
.......Trying 6 on 7,9 [5, 6] |
|||
........Trying 5 on 1,9 [2, 5] |
|||
.........Trying 3 on 3,8 [3, 7] |
|||
..........Trying 4 on 2,1 [1, 4] |
|||
..........Trying 1 on 2,1 [1, 4] |
|||
..........Backtrack, path unsolvable... (on 2 1) |
|||
.........Trying 7 on 3,8 [3, 7] |
|||
..........Trying 3 on 3,7 [1, 3] |
|||
..........Trying 1 on 3,7 [1, 3] |
|||
..........Backtrack, path unsolvable... (on 3 7) |
|||
.........Backtrack, path unsolvable... (on 3 8) |
|||
........Trying 2 on 1,9 [2, 5] |
|||
.........Trying 3 on 3,8 [3, 7] |
|||
..........Trying 7 on 2,7 [1, 7] |
|||
..........Trying 1 on 2,7 [1, 7] |
|||
...........Trying 4 on 2,1 [2, 4] |
|||
...........Trying 2 on 2,1 [2, 4] |
|||
...........Solved... (2 on 2,1) |
|||
..........Solved... (1 on 2,7) |
|||
.........Solved... (3 on 3,8) |
|||
........Solved... (2 on 1,9) |
|||
.......Solved... (6 on 7,9) |
|||
......Solved... (3 on 8,9) |
|||
.....Solved... (6 on 8,3) |
|||
....Solved... (5 on 8,1) |
|||
...Solved... (1 on 9,8) |
|||
..Solved... (7 on 9,9) |
|||
.Solved... (3 on 9,2) |
|||
Solved... (8 on 9,1) |
|||
--------------------------------------------- |
|||
9 5 4 1 3 7 6 8 2 |
|||
2 7 3 6 8 4 1 9 5 |
|||
1 6 8 2 9 5 7 3 4 |
|||
4 9 5 7 2 8 3 6 1 |
|||
6 8 1 4 5 3 2 7 9 |
|||
3 2 7 9 6 1 5 4 8 |
|||
7 4 9 3 1 2 8 5 6 |
|||
5 1 6 8 7 9 4 2 3 |
|||
8 3 2 5 4 6 9 1 7 |
|||
</pre> |
|||
=={{header|Rascal}}== |
=={{header|Rascal}}== |
||
Line 9,961: | Line 9,961: | ||
RDN ; get rid of the sum from the stack |
RDN ; get rid of the sum from the stack |
||
RTN |
RTN |
||
</pre> |
</pre> |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
Line 11,991: | Line 11,991: | ||
</pre> |
</pre> |
||
=={{ |
=={{header|VBA}}== |
||
{{trans|Fortran}} |
{{trans|Fortran}} |
||
<lang VB>Dim grid(9, 9) |
<lang VB>Dim grid(9, 9) |