Sudoku: Difference between revisions

=={{header|C#}}==

=={{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>

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