Sudoku: Difference between revisions
Added Uiua solution
(Added Uiua solution) |
|||
(23 intermediate revisions by 11 users not shown) | |||
Line 12:
{{trans|Kotlin}}
<
solved = 0B
grid = [0] * 81
Line 83:
‘000036040’]
Sudoku(rows).solve()</
{{out}}
Line 118:
=={{header|8th}}==
<
\
\ Simple iterative backtracking Sudoku solver for 8th
Line 265:
"No solution!\n" .
then ;
</syntaxhighlight>
=={{header|Ada}}==
{{trans|C++}}
<
with Ada.Text_IO;
Line 378:
solve( sudoku_ar );
end Sudoku;
</syntaxhighlight>
{{out}}
Line 401:
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny].}}
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}
<
MODE BOX = [3, 3]CHAR;
Line 495:
"__1__6__9"))
END CO
)</
{{out}}
<pre>
Line 515:
=={{header|AutoHotkey}}==
<
SetBatchLines, -1
SetTitleMatchMode, 3
Line 658:
r .= SubStr(p, A_Index, 1) . "|"
return r
}</
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f SUDOKU_RC.AWK
BEGIN {
Line 849:
}
function error(message) { printf("error: %s\n",message) ; errors++ }
</syntaxhighlight>
{{out}}
<pre>
Line 886:
{{works with|BBC BASIC for Windows}}
[[Image:sudoku_bbc.gif|right]]
<
*FONT Arial,28
Line 990:
ENDIF
NEXT
= D%</
=={{header|BCPL}}==
<
// Implemented by Martin Richards.
Line 1,388:
{ count := count + 1
prboard()
}</
=={{header|Befunge}}==
Line 1,394:
Input should be provided as a sequence of 81 digits (optionally separated by whitespace), with zero representing an unknown value.
<
2%v|:p+9/9\%9:\p\g02\1p\g01\1:p\g00\1:+8:\p02+*93+*3/<>\20g\g#:
v<+>:0\`>v >\::9%:9+00p3/\9/:99++10p3/3*+39*+20p\:8+::00g\g2%\^
Line 1,401:
p|<$0.0^!g+:#9/9<^@ ^,>#+5<5_>#!<>#$0"------+-------+-----":#<^
<>v$v1:::0<>"P"`!^>0g#0v#p+9/9\%9:p04:\pg03g021pg03g011pg03g001
::>^_:#<0#!:p#-\#1:#g0<>30g010g30g020g30g040g:9%\:9/9+\01-\1+0:</
{{in}}
Line 1,431:
=={{header|Bracmat}}==
The program:
<
Solves any 9x9 sudoku, using backtracking.
Line 1,619:
. new$((its.sudoku),!arg):?puzzle
& (puzzle..Display)$
);</
Solve a sudoku that is hard for a brute force solver:
<
, (.- - - - - - - - -)
(.- - - - - 3 - 8 5)
Line 1,631:
(.- - 2 - 1 - - - -)
(.- - - - 4 - - - 9)
);</
Solution:
<pre>|~~~|~~~|~~~|
Line 1,651:
The following code is really only good for size 3 puzzles. A longer, even less readable version [[Sudoku/C|here]] could handle size 4s.
<
void show(int *x)
Line 1,717:
return 0;
}</
=={{header|C sharp|C#}}==
===Backtracking===
{{trans|Java}}
<
class SudokuSolver
Line 1,824:
Console.Read();
}
}</
=== Best First Search===
<!-- By Martin Freedman, 20/11/2021 -->
<
using static System.Linq.Enumerable;
using System.Collections.Generic;
Line 1,904:
}
}
}</
Usage
<
using static System.Linq.Enumerable;
using static System.Console;
Line 1,941:
}
}
}</
Output
<pre>693784512
Line 1,960:
{{libheader|Microsoft Solver Foundation}}
<!-- By Nigel Galloway, Jan 29, 2012 -->
<
namespace Sudoku
Line 2,032:
}
}
}</
Produces:
<pre>
Line 2,049:
==="Dancing Links"/Algorithm X===
<
using System.Collections.Generic;
using System.Text;
Line 2,327:
public static string DelimitWith<T>(this IEnumerable<T> source, string separator) => string.Join(separator, source);
}</
{{out}}
<pre>
Line 2,352:
=={{header|C++}}==
{{trans|Java}}
<
using namespace std;
Line 2,443:
ss.solve();
return EXIT_SUCCESS;
}</
=={{header|Clojure}}==
<
(:use [clojure.pprint :only (cl-format)]))
Line 2,469:
(if (= x (dec c))
(recur ng 0 (inc y))
(recur ng (inc x) y)))))))</
<
(solve [[3 9 4 0 0 2 6 7 0]
[0 0 0 3 0 0 4 0 0]
Line 2,491:
8 2 6 4 1 9 7 3 5
nil</
=={{header|Common Lisp}}==
A simple solver without optimizations (except for pre-computing the possible entries of a cell).
<
(dotimes (i 9 neighbors)
(let ((x (aref grid row i)))
Line 2,534:
(setf (aref grid row column) choice)
(when (eq grid (solve grid row (1+ column)))
(return grid))))))</
Example:
<pre>> (defparameter *puzzle*
Line 2,564:
Based on the Java implementation presented in the video "[https://www.youtube.com/watch?v=mcXc8Mva2bA Create a Sudoku Solver In Java...]".
<
def isNumberInRow(board, number, row)
Line 2,637:
printBoard(board)
end
</syntaxhighlight>
{{out}}
<pre>
Line 2,666:
=={{header|Curry}}==
Copied from [http://www.informatik.uni-kiel.de/~curry/examples/ Curry: Example Programs].
<
--- Solving Su Doku puzzles in Curry with FD constraints
---
Line 2,728:
" 5 7 921 ",
" 64 9 ",
" 2 438"]</
Line 2,734:
{{Works with|PAKCS}}
Minimal w/o read or show utilities.
<
import Constraint (allC)
import List (transpose)
Line 2,767:
, [7,_,_,6,_,_,5,_,_]
]
main | sudoku xs = xs where xs = test</
{{Out}}
<pre>Execution time: 0 msec. / elapsed: 10 msec.
Line 2,775:
{{trans|C++}}
A little over-engineered solution, that shows some strong static typing useful in larger programs.
<
std.ascii, std.typecons;
Line 2,901:
else
solution.get.representSudoku.writeln;
}</
{{out}}
<pre>8 5 . | . . 2 | 4 . .
Line 2,929:
===Short Version===
Adapted from: http://code.activestate.com/recipes/576725-brute-force-sudoku-solver/
<
const(int)[] solve(immutable int[] s) pure nothrow @safe {
Line 2,962:
0, 0, 0, 0, 3, 6, 0, 4, 0];
writefln("%(%s\n%)", problem.solve.chunks(9));
}</
{{out}}
<pre>[8, 5, 9, 6, 1, 2, 4, 3, 7]
Line 2,976:
===No-Heap Version===
This version is similar to the precedent one, but it shows idioms to avoid memory allocations on the heap. This is enforced by the use of the @nogc attribute.
<
Nullable!(const ubyte[81]) solve(in ubyte[81] s) pure nothrow @safe @nogc {
Line 3,017:
0, 0, 0, 0, 3, 6, 0, 4, 0];
writefln("%(%s\n%)", problem.solve.get[].chunks(9));
}</
Same output.
=={{header|Delphi}}==
Example taken from C++
<
TIntArray = array of Integer;
Line 3,146:
ShowMessage('Solved!');
end;
end;</
Usage:
<
SudokuSolver: TSudokuSolver;
begin
Line 3,165:
FreeAndNil(SudokuSolver);
end;
end;</
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
len
len
len box[] 90
len grid[] 82
#
for pos
if pos mod 9 =
s$
.
dig = number inp[(pos - 1) mod 9 + 1]
if dig > 0
grid[pos] = dig
r = (pos - 1) div 9
c = (pos - 1) mod 9
b = r div 3 * 3 + c div 3
row[r * 10 + dig] = 1
col[c * 10 + dig] = 1
box[b * 10 + dig] = 1
.
.
.
#
for i
write grid[i] & " "
if i mod 3 =
write " "
.
if i mod 9 =
print ""
.
if i mod 27 =
print ""
.
.
.
#
while grid[pos] <> 0
pos += 1
.
if pos
# solved
.
r = (pos - 1) div 9
c = (pos - 1) mod 9
b = r div 3 * 3 + c div 3
r *= 10
c *= 10
b *= 10
for d = 1 to 9
if row[r + d] = 0 and col[c + d] = 0 and box[b + d] = 0
grid[pos] = d
row[r + d] = 1
col[c + d] = 1
box[b + d] = 1
row[r + d] = 0
col[c + d] = 0
box[b + d] = 0
.
.
grid[pos] = 0
.
#
input_data
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
7 9 0 0 0 0
0
9 6 0 0 1 0 3 0 0
0 5 0 6 9 0 0 1 0
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Erlang}}
<
def display( grid ), do: ( for y <- 1..9, do: display_row(y, grid) )
Line 3,405 ⟶ 3,421:
{{3, 8}, 2}, {{5, 8}, 1},
{{5, 9}, 4}, {{9, 9}, 9}]
Sudoku.task( difficult )</
{{out}}
Line 3,465 ⟶ 3,481:
=={{header|Erlang}}==
I first try to solve the Sudoku grid without guessing. For the guessing part I eschew spawning a process for each guess, instead opting for backtracking. It is fun trying new things.
<syntaxhighlight lang="erlang">
-module( sudoku ).
Line 3,628 ⟶ 3,644:
display( Solved ),
io:nl().
</syntaxhighlight>
{{out}}
<pre>
Line 3,712 ⟶ 3,728:
0 is the empty cell.
<syntaxhighlight lang="erre">
!--------------------------------------------------------------------
! risolve Sudoku: in input il file SUDOKU.TXT
Line 4,119 ⟶ 4,135:
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
===Backtracking===
<!-- By Martin Freedman, 26/11/2021 -->
<
//Helpers
Line 4,197 ⟶ 4,213:
/// solve sudoku using simple backtracking
let solve grid = grid |> parseGrid >>= flip backtracker (Some "A1")</
'''Usage:'''
<
open SudokuBacktrack
Line 4,211 ⟶ 4,227:
printfn "Press any key to exit"
Console.ReadKey() |> ignore
0</
{{Output}}<pre>
Puzzle:
Line 4,240 ⟶ 4,256:
===Constraint Satisfaction (Norvig)===
<!-- By Martin Freedman, 27/11/2021 -->
<
// using array O(1) lookup & mutable instead of map O(logn) immutable - now 6 times faster
module SudokuCPSArray
Line 4,364 ⟶ 4,380:
let solveNoSearch: string -> string = solver applyCPS
let solveWithSearch: string -> string = solver (applyCPS >> (Option.bind search))
let solveWithSearchToMapOnly:string -> int[][] option = run None id (applyCPS >> (Option.bind search)) </
'''Usage'''<
open SudokuCPSArray
open System.Diagnostics
Line 4,412 ⟶ 4,428:
printfn "Some sudoku17 puzzles failed"
Console.ReadKey() |> ignore
0</
{{Output}}Timings run on i7500U @2.75Ghz CPU, 16GB RAM<pre>Easy board solution automatic with constraint propagation
4 8 3 |9 2 1 |6 5 7
Line 4,472 ⟶ 4,488:
===SLPsolve===
<
// Solve Sudoku Like Puzzles. Nigel Galloway: September 6th., 2018
let fN y n g=let _q n' g'=[for n in n*n'..n*n'+n-1 do for g in g*g'..g*g'+g-1 do yield (n,g)]
Line 4,501 ⟶ 4,517:
List.map2(fun n g->List.map(fun(n',g')->((n',g'),n))g) (List.rev n) g|>List.concat|>List.sortBy (fun ((_,n),_)->n)|>List.groupBy(fun ((n,_),_)->n)|>List.sortBy(fun(n,_)->n)
|>List.iter(fun (_,n)->n|>Seq.fold(fun z ((_,g),v)->[z..g-1]|>Seq.iter(fun _->printf " |");printf "%s|" v; g+1 ) 0 |>ignore;printfn "")
</syntaxhighlight>
'''Usage:'''
Given sud1.csv:
Line 4,516 ⟶ 4,532:
</pre>
then
<
let n=SLPsolve (fE ([1..9]|>List.map(string)) 9 3 3 "sud1.csv")
printSLP ([1..9]|>List.map(string)) (Seq.item 0 n)
</syntaxhighlight>
{{out}}
<pre>
Line 4,535 ⟶ 4,551:
=={{header|Forth}}==
{{works with|4tH|3.60.0}}
<
include lib/istype.4th
include lib/argopen.4th
Line 4,898 ⟶ 4,914:
;
sudoku</
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
This implementation uses a brute force method. The subroutine <code>solve</code> recursively checks valid entries using the rules defined in the function <code>is_safe</code>. When <code>solve</code> is called beyond the end of the sudoku, we know that all the currently entered values are valid. Then the result is displayed.
<
implicit none
Line 5,000 ⟶ 5,016:
end subroutine pretty_print
end program sudoku</
{{out}}<pre>
+-----+-----+-----+
Line 5,033 ⟶ 5,049:
=={{header|FreeBASIC}}==
{{trans|VBA}}
<
Function isSafe(i As Integer, j As Integer, n As Integer) As Boolean
Line 5,119 ⟶ 5,135:
If (i Mod 3 = 0) Then Print !"\n---------+---------+---------" Else Print
Next i
Sleep</
{{out}}
<pre>
Line 5,141 ⟶ 5,157:
=={{header|FutureBasic}}==
First is a short version:
<
include "Util_Containers.incl"
begin globals
end globals
BeginCDeclaration
short solve_sudoku(short i);
short check_sudoku(short r, short c);
CFMutableStringRef print_sudoku();
EndC
BeginCFunction
short sudoku[9][9] = {
{3,0,0,0,0,1,4,0,9},
{7,0,0,0,0,4,2,0,0},
{0,5,0,2,0,0,0,1,0},
{5,7,0,0,4,3,0,6,0},
{0,9,0,0,0,0,0,3,0},
{0,6,0,7,9,0,0,8,5},
{0,8,0,0,0,5,0,4,0},
{0,0,6,4,0,0,0,0,7},
{9,0,5,6,0,0,0,0,3},
};
short check_sudoku( short r, short c )
{
short i;
short rr, cc;
{
if (i
if (i != r && sudoku[i][c] == sudoku[r][c]) return 0;
rr = r/3 * 3 + i/3;
cc = c/3 * 3 + i%3;
if ((rr != r || cc != c) && sudoku[rr][cc] == sudoku[r][c]) return 0;
}
return
}
short solve_sudoku( short i )
{
short
if (i < 0) return
else if (i >= 81) return -1;
r = i / 9;
c
if (sudoku[r][c])
return check_sudoku(r, c) && solve_sudoku(i + 1);
else
for (sudoku[r][c] = 9; sudoku[r][c] > 0; sudoku[r][c]--)
{
if ( solve_sudoku(i) ) return -1;
}
return 0;
}
CFMutableStringRef print_sudoku()
{
short i, j;
CFMutableStringRef mutStr;
mutStr = CFStringCreateMutable( kCFAllocatorDefault, 0 );
for (i = 0; i < 9; i++)
{
for (j = 0; j < 9; j++)
{
CFStringAppendFormat( mutStr, NULL, (CFStringRef)@" %d", sudoku[i][j] );
}
CFStringAppendFormat( mutStr, NULL, (CFStringRef)@"\r" );
}
return( mutStr );
}
EndC
Line 5,231 ⟶ 5,244:
toolbox fn print_sudoku() = CFMutableStringRef
gC = " "
Line 5,243 ⟶ 5,256:
print : print "Sudoku solved:" : print
if ( solution )
gC = " "
cfRef = fn print_sudoku()
fn ContainerCreateWithCFString( cfRef, gC )
print gC
else
print "No solution found"
end if
HandleEvents
</syntaxhighlight>
Output:
Line 5,282 ⟶ 5,297:
More code in this one, but faster execution:
<pre>
begin globals
_digits = 9
Line 5,293 ⟶ 5,305:
begin record Board
dim &&
end record
CFTimeInterval t
end globals
local mode
local fn CopyBoard( source as ^Board, dest as ^Board )
BlockMoveData( source, dest, sizeof( Board ) )
dest.previousBoard = source // linked list
end fn
local fn prepare( b as ^Board )
short i, j, n
for i = 1 to _digits
for
for
b.match[i, j] = 0
b.
next n
next
next
end fn
local fn printBoard( b as ^Board )
short i, j
for i = 1 to _digits
for
Print b.match[i, j];
next j
print
next i
end fn
local fn verifica( b as ^Board )
short i, j, n, first, x, y, ii
Boolean check
check = _true
for i = 1 to _digits
for
if ( b.match[i, j] == 0 )
check = _false
for n = 1 to _digits
if ( b.f[i, j, n] != _false )
check = _true
end if
next n
if ( check == _false ) then exit fn
end if
next j
next
check = _true
for j = 1 to _digits
for
for i = 1 to _digits
if ( b.match[i, j] == n )
else
check = _false
exit fn
end if
end if
next i
next
next
for i = 1 to _digits
for
for j = 1 to _digits
if ( b.match[i, j] == n )
else
check = _false
exit fn
end if
end if
next j
next
next
for x = 0 to ( _nSetH - 1 )
for
for ii = 0 to ( _digits - 1 )
i = x * _setH + ii mod _setH + 1
else
check = _false
exit fn
end if
end if
next ii
next
next
end fn = check
local fn setCell( b as ^Board, x as short, y as short, n as short) as boolean
b.match[x, y] = n
for i = 1 to _digits
b.f[x, i, n] = _false
b.f[i, y, n] = _false
next i
rx = (x - 1) / _setH
ry = (y - 1) / _setV
for i = 1 to _setH
for j = 1 to _setV
b.f[ rx * _setH + i, ry * _setV + j, n ] = _false
next j
next i
check = fn verifica( #b )
if ( check == _false ) then exit fn
end fn = check
local fn solve( b as ^Board )
check = _true
for i = 1 to _digits
for j = 1 to _digits
first = 0
for n = 1 to _digits
first = n
else
first = -1
exit for
end if
end if
next n
check = fn setCell( #b, i, j, first )
if ( check == _false ) then exit fn
check = fn solve(#b)
if ( check == _false ) then exit fn
end if
end if
next j
next i
for i = 1 to _digits
for n = 1 to _digits
first = 0
for j = 1 to _digits
if ( b.match[i, j] == n ) then exit for
first = j
else
first = -1
exit for
end if
end if
next j
check = fn setCell( #b, i, first, n )
if ( check == _false ) then exit fn
check = fn solve(#b)
if ( check == _false ) then exit fn
end if
next n
next i
for j = 1 to _digits
for n = 1 to _digits
first = 0
for i = 1 to _digits
if ( b.match[i, j] == n ) then exit for
first = i
else
first = -1
exit for
end if
end if
next i
check = fn setCell( #b, first, j, n )
if ( check == _false ) then exit fn
check = fn solve(#b)
if ( check == _false ) then exit fn
end if
next n
next j
for x = 0 to ( _nSetH - 1 )
for y = 0 to ( _nSetV - 1 )
for n = 1 to _digits
first = 0
for ii = 0 to ( _digits - 1 )
i = x * _setH + ii mod _setH + 1
j = y * _setV + ii / _setH + 1
if ( b.match[i, j] == n ) then exit for
first = n
ppi = i
ppj = j
else
first = -1
exit for
end if
end if
next ii
check = fn setCell( #b, ppi, ppj, n )
if ( check == _false ) then exit fn
check = fn solve(#b)
if ( check == _false ) then exit fn
end if
next n
next y
next x
end fn = check
local fn resolve( b as ^Board )
check = fn solve(b)
exit fn
end if
daFinire = _false
for i = 1 to _digits
for j = 1 to _digits
daFinire = _true
for n = 1 to _digits
fn CopyBoard( b, @localBoard )
check = fn setCell(@localBoard, i, j, n)
check = fn resolve( @localBoard )
fn CopyBoard( @localBoard, b )
exit fn
end if
end if
end if
next n
end if
next j
next i
else
check = -1
end if
end fn = check
fn prepare( @quiz )
Line 5,655 ⟶ 5,642:
DATA 2,8,0,1,3,0,0,0,0
for i = 1 to _digits
for j = 1 to _digits
read d
fn setCell(@quiz, j, i, d)
next j
next i
Line 5,666 ⟶ 5,653:
fn printBoard( @quiz )
print : print "-------------------" : print
t = fn
check = fn resolve(@quiz)
t = (fn
if ( check )
print "solution:"; str$( t
else
print "No solution found"
end if
fn printBoard( @quiz )
HandleEvents
</pre>
Line 5,712 ⟶ 5,701:
Input to function solve is an 81 character string.
This seems to be a conventional computer representation for Sudoku puzzles.
<
import "fmt"
Line 5,913 ⟶ 5,902:
}
c.r.l, c.l.r = &c.x, &c.x
}</
{{out}}
<pre>
Line 5,946 ⟶ 5,935:
Imprime todas las soluciones posibles, sale con un error, pero funciona.
<
'Solution:'
;'2 8 4 3 7 5 1 6 9
Line 5,960 ⟶ 5,949:
~]{:@0?:^~!{@p}*10,@9/^9/=-@^9%>9%-@3/^9%3/>3%3/^27/={+}*-{@^<\+@1^+>+}/1}do
</syntaxhighlight>
=={{header|Groovy}}==
Line 5,968 ⟶ 5,957:
I consider this a "brute force" solution of sorts, in that it is the same method I use when solving Sudokus manually.
<
class GridException extends Exception {
Line 6,035 ⟶ 6,024:
}
grid
}</
'''Test/Benchmark Cases'''
Mentions of ''"exceptionally difficult" example in Wikipedia'' refer to this (former) page: [[https://en.wikipedia.org/w/index.php?title=Sudoku_solving_algorithms&oldid=410240496#Exceptionally_difficult_Sudokus_.28hardest_Sudokus.29 Exceptionally difficult Sudokus]]
<
//Used in Curry solution: ~ 0.1 seconds
'819..5.....2...75..371.4.6.4..59.1..7..3.8..2..3.62..7.5.7.921..64...9.....2..438',
Line 6,102 ⟶ 6,091:
solution.each { println it }
println "\nELAPSED: ${elapsed} seconds"
}</
{{out}} (last only):
Line 6,136 ⟶ 6,125:
=={{header|Java}}==
<
{
private int mBoard[][];
Line 6,254 ⟶ 6,243:
}
}
}</
{{out}}
Line 6,293 ⟶ 6,282:
====ES6====
<
/**
* The doubly-doubly circularly linked data object.
Line 6,566 ⟶ 6,555:
search(H, []);
};
</syntaxhighlight>
<syntaxhighlight lang="javascript">[
'819..5.....2...75..371.4.6.4..59.1..7..3.8..2..3.62..7.5.7.921..64...9.....2..438',
'53..247....2...8..1..7.39.2..8.72.49.2.98..7.79.....8.....3.5.696..1.3...5.69..1.',
Line 6,593 ⟶ 6,582:
let s = new Array(Math.pow(n, 4)).fill('.').join('');
reduceGrid(s);
</syntaxhighlight>
<pre>+-------+-------+-------+
Line 6,622 ⟶ 6,611:
| 7 8 2 | 6 9 3 | 5 4 1 |
+-------+-------+-------+
</pre>
=={{header|jq}}==
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq'''
'''Also works with fq, a Go implementation of a large subset of jq'''
The two solutions presented here take advantage of jq's built-in backtracking
mechanism.
The first solution uses a naive backtracking algorithm which can readily be modified to include more sophisticated
strategies.
The second solution modifies `next_row` to use a simple greedy algorithm,
namely, "select the row with the fewest gaps".
For the `tarx0134` problem (taken from the
[https://en.wikipedia.org/w/index.php?title=Sudoku_solving_algorithms#Exceptionally_difficult_Sudokus_.28hardest_Sudokus.29 Wikipedia collection] but googleable by that name),
the running time (u+s) is reduced from 264s to 180s on my 3GHz machine.
The memory usage statistics as produced by `/usr/bin/time -lp`
are also shown in the output section below.
<syntaxhighlight lang=jq>
## Utility Functions
def div($b): (. - (. % $b)) / $b;
def count(s): reduce s as $_ (0; .+1);
def row($i): .[$i];
def col($j): transpose | row($j);
# pretty print
def pp: .[:3][],"", .[3:6][], "", .[6:][];
# Input: 9 x 9 matrix
# Output: linear array corresponding to the specified 3x3 block using IO=0:
# 0,0 0,1 0,2
# 1,0 1,1 1,2
# 2,0 2,1 2,2
def block($i;$j):
def x: range(0;3) + 3*$i;
def y: range(0;3) + 3*$j;
[.[x][y]];
# Output: linear block containing .[$i][$j]
def blockOf($i;$j):
block($i|div(3); $j|div(3));
# Input: the entire Sudoku matrix
# Output: the update matrix after solving for row $i
def solveRow($i):
def s:
(.[$i] | index(0)) as $j
| if $j
then ((( [range(1;10)] - row($i)) - col($j)) - blockOf($i;$j) ) as $candidates
| if $candidates|length == 0 then empty
else $candidates[] as $x
| .[$i][$j] = $x
| s
end
else .
end;
s;
def distinct: map(select(. != 0)) | length - (unique|length) == 0;
# Is the Sudoku valid?
def valid:
. as $in
| length as $l
| all(.[]; distinct) and
all( range(0;9); . as $i | $in | col($i) | distinct ) and
all( range(0;3); . as $i | all(range(0;3); . as $j
| $in | block($i;$j) | distinct ));
# input: the full puzzle in its current state
# output: null if there is no candidate next row
def next_row:
first( range(0; length) as $i | select(row($i)|index(0)) | $i) // null;
def solve(problem):
def s:
next_row as $ix
| if $ix then solveRow($ix) | s
else .
end;
if problem|valid then first(problem|s) | pp
else "The Sukoku puzzle is invalid."
end;
# Rating Program: dukuso's suexratt
# Rating: 3311
# Poster: tarek
# Label: tarx0134
# ........8..3...4...9..2..6.....79.......612...6.5.2.7...8...5...1.....2.4.5.....3
def tarx0134:
[[0,0,0,0,0,0,0,0,8],
[0,0,3,0,0,0,4,0,0],
[0,9,0,0,2,0,0,6,0],
[0,0,0,0,7,9,0,0,0],
[0,0,0,0,6,1,2,0,0],
[0,6,0,5,0,2,0,7,0],
[0,0,8,0,0,0,5,0,0],
[0,1,0,0,0,0,0,2,0],
[4,0,5,0,0,0,0,0,3]];
# An invalid puzzle, for checking `valid`:
def unsolvable:
[[3,9,4,3,0,2,6,7,0],
[0,0,0,3,0,0,4,0,0],
[5,0,0,6,9,0,0,2,0],
[0,4,5,0,0,0,9,0,0],
[6,0,0,0,0,0,0,0,7],
[0,0,7,0,0,0,5,8,0],
[0,1,0,0,6,7,0,0,8],
[0,0,9,0,0,8,0,0,0],
[0,2,6,4,0,0,7,3,5]] ;
solve(tarx0134)
</syntaxhighlight>
====Greedy Algorithm====
Replace `def next_row:` with the following definition:
<syntaxhighlight lang=jq>
# select a row with the fewest number of unknowns
def next_row:
length as $len
| . as $in
| reduce range(0;length) as $i ([];
. + [ [ count( $in[$i][] | select(. != 0)), $i] ] )
| map(select(.[0] != $len))
| if length == 0 then null
else max_by(.[0]) | .[1]
end ;
</syntaxhighlight>
{{output}}
For the naive next_row:
<pre>
[6,2,1,9,4,3,7,5,8]
[7,8,3,6,1,5,4,9,2]
[5,9,4,7,2,8,3,6,1]
[1,4,2,8,7,9,6,3,5]
[3,5,7,4,6,1,2,8,9]
[8,6,9,5,3,2,1,7,4]
[2,3,8,1,9,7,5,4,6]
[9,1,6,3,5,4,8,2,7]
[4,7,5,2,8,6,9,1,3]
# Summary performance statistics:
user 260.89
sys 3.32
2240512 maximum resident set size
1302528 peak memory footprint
</pre>
For the greedy next_row algorithm, jq produces the same solution
with the following performance statistics:
<pre>
user 177.94
sys 2.12
2224128 maximum resident set size
1277952 peak memory footprint
</pre>
gojq stats for the greedy algorithm:
<pre>
user 62.19
sys 7.44
7458418688 maximum resident set size
7683284992 peak memory footprint
</pre>
fq stats for the greedy algorithm:
<pre>
user 73.56
sys 5.34
6084091904 maximum resident set size
6436892672 peak memory footprint
</pre>
=={{header|Julia}}==
<
id, im = div(i, 9), mod(i, 9)
jd, jm = div(j, 9), mod(j, 9)
Line 6,648 ⟶ 6,818:
for i in 1:81
if grid[i] == 0
t = Dict{Int64,
for j in 1:81
Line 6,691 ⟶ 6,861:
0, 5, 0, 6, 9, 0, 0, 1, 0]
solve_sudoku(display, grid)</
{{out}}
<pre>
Line 6,709 ⟶ 6,879:
=={{header|Kotlin}}==
{{trans|C++}}
<
class Sudoku(rows: List<String>) {
Line 6,792 ⟶ 6,962:
)
Sudoku(rows).solve()
}</
{{out}}
Line 6,827 ⟶ 6,997:
=={{header|Lua}}==
===without FFI, slow===
<
--based on a branch and bound solution
--fields are not tried in plain order
Line 7,009 ⟶ 7,179:
if x then
return printer(x)
end</
Input:
<pre>
Line 7,041 ⟶ 7,211:
Time with luajit: 9.245s
===with FFI, fast===
<
ffi=require"ffi"
local printf=function(fmt, ...) io.write(string.format(fmt, ...)) end
Line 7,109 ⟶ 7,279:
... .8. .79
]])
end</
{{out}}
<pre>> time ./sudoku_fast.lua
Line 7,128 ⟶ 7,298:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
NestWhile[
Join @@ Table[
Line 7,137 ⟶ 7,307:
Extract[Partition[s, {3, 3}], Quotient[#, 3, -2]]]} & /@
Position[s, 0, {2}],
Length@Last@# &], {s, #}] &, {sudoku}, ! FreeQ[#, 0] &]</
Example:
<syntaxhighlight lang="text">solve[{{9, 7, 0, 3, 0, 0, 0, 6, 0},
{0, 6, 0, 7, 5, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 8, 0, 5, 0},
Line 7,147 ⟶ 7,317:
{7, 0, 0, 0, 2, 5, 0, 0, 0},
{0, 0, 2, 0, 1, 0, 0, 0, 8},
{0, 4, 0, 0, 0, 7, 3, 0, 0}}]</
{{out}}
<pre>{{{9, 7, 5, 3, 4, 2, 8, 6, 1}, {8, 6, 1, 7, 5, 9, 4, 3, 2}, {3, 2, 4,
Line 7,158 ⟶ 7,328:
For this to work, this code must be placed in a file named "sudokuSolver.m"
<
%Define what each of the sub-boxes of the sudoku grid are by defining
Line 7,510 ⟶ 7,680:
%% End of program
end %end sudokuSolver</
[http://www.menneske.no/sudoku/eng/showpuzzle.html?number=6903541 Test Input]:
All empty cells must have a value of NaN.
<
1 NaN NaN NaN NaN NaN NaN 3 NaN
NaN NaN 4 NaN NaN NaN NaN 7 NaN
Line 7,521 ⟶ 7,691:
NaN 2 NaN NaN NaN NaN NaN NaN NaN
NaN 8 NaN NaN NaN 9 2 NaN NaN
NaN NaN NaN 2 5 NaN NaN NaN 6]</
[http://www.menneske.no/sudoku/eng/solution.html?number=6903541 Output]:
<
7 6 5 4 8 3 9 2 1
Line 7,533 ⟶ 7,703:
9 2 6 1 4 7 5 8 3
5 8 1 3 6 9 2 4 7
4 7 3 2 5 8 1 9 6</
=={{header|Nim}}==
{{trans|Kotlin}}
<
type
Line 7,611 ⟶ 7,781:
var puzzle = Sudoku()
puzzle.init(rows)
puzzle.solve()</
{{out}}
Line 7,644 ⟶ 7,814:
=={{header|OCaml}}==
uses the library [http://ocamlgraph.lri.fr/index.en.html ocamlgraph]
<
Copyright 2004-2007 Sylvain Conchon, Jean-Christophe Filliatre, Julien Signoles
Line 7,713 ⟶ 7,883:
module C = Coloring.Mark(G)
let () = C.coloring g 9; display ()</
=={{header|Oz}}==
Using built-in constraint propagation and search.
<
%% a puzzle is a function that returns an initial board configuration
fun {Puzzle1}
Line 7,800 ⟶ 7,970:
end
in
{Inspect {Solve Puzzle1}.1}</
=={{header|PARI/GP}}==
Build plugin for PARI's function interface from C code: sudoku.c
<
typedef int SUDOKU [9][9];
Line 7,875 ⟶ 8,045:
return gen_0; /* no solution */
}
</syntaxhighlight>
Compile plugin: gcc -O2 -Wall -fPIC -shared sudoku.c -o libsudoku.so -lpari
Install plugin from home directory and play:
<
Output:<pre> gp > S=[5,3,0,0,7,0,0,0,0;6,0,0,1,9,5,0,0,0;0,9,8,0,0,0,0,6,0;8,0,0,0,6,0,0,0,3;4,0,0,8,0,3,0,0,1;7,0,0,0,2,0,0,0,6;0,6,0,0,0,0,2,8,0;0,0,0,4,1,9,0,0,5;0,0,0,0,8,0,0,7,9]
Line 7,907 ⟶ 8,077:
{{works with|Free Pascal}}
Simple backtracking implimentation, therefor it must be fast to be competetive.With doReverse = true same sequence for trycell. nearly 5 times faster than [[Sudoku#C|C]]-Version.
<
{$IFDEF FPC}
{$CODEALIGN proc=16,loop=8}
Line 8,163 ⟶ 8,333:
Outfield(solF);
writeln(86400*1000*(T1-T0)/k:10:3,' ms Test calls :',callCnt/k:8:0);
end.</
{{out}}
<pre>
Line 8,199 ⟶ 8,369:
=={{header|Perl}}==
<
use integer;
use strict;
Line 8,238 ⟶ 8,408:
}
}
solve();</
{{out}}
<pre>
Line 8,256 ⟶ 8,426:
=={{header|Phix}}==
Simple brute force solution. Generally quite good but will struggle on some puzzles (eg see "the beast" below)
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"""
Line 8,308 ⟶ 8,478:
<span style="color: #000000;">brute_solve</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n(solved in %3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span>
<!--</
{{out}}
<pre>
Line 8,326 ⟶ 8,496:
contains 339 puzzles, can be run as a command-line or gui program, check for multiple solutions, and produce
a more readable single-puzzle output (example below).
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #000080;font-style:italic;">-- Working directly on 81-character strings ultimately proves easier: Originally I
Line 8,970 ⟶ 9,140:
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">()</span>
<!--</
{{out}}
<pre>
Line 9,039 ⟶ 9,209:
=={{header|PHP}}==
{{trans|C++}}
<
protected $grid = [];
protected $emptySymbol;
Line 9,163 ⟶ 9,333:
$solver = new SudokuSolver('009170000020600001800200000200006053000051009005040080040000700006000320700003900');
$solver->solve();
$solver->display();</
{{out}}
<pre>
Line 9,183 ⟶ 9,353:
Using constraint programming.
<
import cp.
Line 9,209 ⟶ 9,379:
end,
nl.
sudoku(Board) =>
Line 9,222 ⟶ 9,391:
end,
solve([ffd,inout], Vars).
print_board(Board) =>
Line 9,255 ⟶ 9,423:
"....839..1......3...4....7..42.3....6.......4....7..1..2........8...92.....25...6",
"..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686........7..6..5.."
].</syntaxhighlight>
{{out}}
All problems are solved (and proved/checked for unicity) in 0.043s.
<pre>
819..5.....2...75..371.4.6.4..59.1..7..3.8..2..3.62..7.5.7.921..64...9.....2..438
Line 9,288 ⟶ 9,455:
=={{header|PicoLisp}}==
<
### Fields/Board ###
Line 9,369 ⟶ 9,536:
(0 6 0 0 0 0 2 8 0)
(0 0 0 4 1 9 0 0 5)
(0 0 0 0 8 0 0 7 9) ) )</
{{out}}
<pre> +---+---+---+---+---+---+---+---+---+
Line 9,391 ⟶ 9,558:
+---+---+---+---+---+---+---+---+---+
a b c d e f g h i</pre>
<syntaxhighlight lang
{{out}}
<pre> +---+---+---+---+---+---+---+---+---+
Line 9,416 ⟶ 9,583:
=={{header|PL/I}}==
Working PL/I version, derived from the Rosetta Fortran version.
<
declare grid (9,9) fixed (1) static initial (
Line 9,499 ⟶ 9,666:
end sudoku;
</syntaxhighlight>
{{out}}
<pre>
Line 9,533 ⟶ 9,700:
Another PL/I version, reads sudoku from the text data file as 81 character record.
<
*PROCESS MARGINS(1,120) LIBS(SINGLE,STATIC);
*PROCESS OPTIMIZE(2) DFT(REORDER);
Line 9,672 ⟶ 9,839:
end sudoku;
</syntaxhighlight>
=={{header|Prolog}}==
<
sudoku(Rows) :-
Line 9,700 ⟶ 9,867:
[5,_,_,_,_,_,_,7,3],
[_,_,2,_,1,_,_,_,_],
[_,_,_,_,4,_,_,_,9]]).</
===GNU Prolog version===
{{works with|GNU Prolog|1.4.4}}
<
Line 9,757 ⟶ 9,924:
main :- test(T), solve(T), maplist(show,T), halt.
show(X) :- write(X), nl.</
{{Out}}
<pre>[1,2,3,4,5,6,7,8,9]
Line 9,772 ⟶ 9,939:
=={{header|PureBasic}}==
A brute force method is used, it seemed the fastest as well as the simplest.
<
puzzle:
Data.s "394002670"
Line 9,882 ⟶ 10,049:
Input()
CloseConsole()
EndIf</
{{out}}
<pre>+-----+-----+-----+
Line 9,914 ⟶ 10,081:
=={{header|Python}}==
See [http://www2.warwick.ac.uk/fac/sci/moac/currentstudents/peter_cock/python/sudoku/ Solving Sudoku puzzles with Python] for GPL'd solvers of increasing complexity of algorithm.
===Backtrack===
A simple backtrack algorithm -- Quick but may take longer if the grid had been more than 9 x 9
<
def initiate():
box.append([0, 1, 2, 9, 10, 11, 18, 19, 20])
Line 10,000 ⟶ 10,169:
print grid[i*9:i*9+9]
raw_input()
</syntaxhighlight>
===Search + Wave Function Collapse===
A Sudoku solver using search guided by the principles of wave function collapse.
<syntaxhighlight lang="python">
sudoku = [
# cell value # cell number
0, 0, 4, 0, 5, 0, 0, 0, 0, # 0, 1, 2, 3, 4, 5, 6, 7, 8,
9, 0, 0, 7, 3, 4, 6, 0, 0, # 9, 10, 11, 12, 13, 14, 15, 16, 17,
0, 0, 3, 0, 2, 1, 0, 4, 9, # 18, 19, 20, 21, 22, 23, 24, 25, 26,
0, 3, 5, 0, 9, 0, 4, 8, 0, # 27, 28, 29, 30, 31, 32, 33, 34, 35,
0, 9, 0, 0, 0, 0, 0, 3, 0, # 36, 37, 38, 39, 40, 41, 42, 43, 44,
0, 7, 6, 0, 1, 0, 9, 2, 0, # 45, 46, 47, 48, 49, 50, 51, 52, 53,
3, 1, 0, 9, 7, 0, 2, 0, 0, # 54, 55, 56, 57, 58, 59, 60, 61, 62,
0, 0, 9, 1, 8, 2, 0, 0, 3, # 63, 64, 65, 66, 67, 68, 69, 70, 71,
0, 0, 0, 0, 6, 0, 1, 0, 0, # 72, 73, 74, 75, 76, 77, 78, 79, 80
# zero = empty.
]
numbers = {1,2,3,4,5,6,7,8,9}
def options(cell,sudoku):
""" determines the degree of freedom for a cell. """
column = {v for ix, v in enumerate(sudoku) if ix % 9 == cell % 9}
row = {v for ix, v in enumerate(sudoku) if ix // 9 == cell // 9}
box = {v for ix, v in enumerate(sudoku) if (ix // (9 * 3) == cell // (9 * 3)) and ((ix % 9) // 3 == (cell % 9) // 3)}
return numbers - (box | row | column)
initial_state = sudoku[:] # the sudoku is our initial state.
job_queue = [initial_state] # we need the jobqueue in case of ambiguity of choice.
while job_queue:
state = job_queue.pop(0)
if not any(i==0 for i in state): # no missing values means that the sudoku is solved.
break
# determine the degrees of freedom for each cell.
degrees_of_freedom = [0 if v!=0 else len(options(ix,state)) for ix,v in enumerate(state)]
# find cell with least freedom.
least_freedom = min(v for v in degrees_of_freedom if v > 0)
cell = degrees_of_freedom.index(least_freedom)
for option in options(cell, state): # for each option we add the new state to the queue.
new_state = state[:]
new_state[cell] = option
job_queue.append(new_state)
# finally - print out the solution
for i in range(9):
print(state[i*9:i*9+9])
# [2, 6, 4, 8, 5, 9, 3, 1, 7]
# [9, 8, 1, 7, 3, 4, 6, 5, 2]
# [7, 5, 3, 6, 2, 1, 8, 4, 9]
# [1, 3, 5, 2, 9, 7, 4, 8, 6]
# [8, 9, 2, 5, 4, 6, 7, 3, 1]
# [4, 7, 6, 3, 1, 8, 9, 2, 5]
# [3, 1, 8, 9, 7, 5, 2, 6, 4]
# [6, 4, 9, 1, 8, 2, 5, 7, 3]
# [5, 2, 7, 4, 6, 3, 1, 9, 8]
</syntaxhighlight>
This solver found the 45 unknown values in 45 steps.
=={{header|Racket}}==
Line 10,009 ⟶ 10,245:
===Brute Force===
{{trans|Perl}}
<syntaxhighlight lang="raku"
5 3 0 0 2 4 7 0 0
0 0 2 0 0 0 8 0 0
Line 10,049 ⟶ 10,285:
}
}
solve;</
{{out}}
Line 10,067 ⟶ 10,303:
This is an alternative solution that uses a more ellaborate set of choices instead of brute-forcing it.
<syntaxhighlight lang="raku"
# In this code, a sudoku puzzle is represented as a two-dimentional
# array. The cells that are not yet solved are represented by yet
Line 10,288 ⟶ 10,524:
}
}
}</
{{out}}
Line 10,306 ⟶ 10,542:
A sudoku is represented as a matrix, see Rascal solutions to matrix related problems for examples.
<
import vis::Figure;
import vis::Render;
Line 10,389 ⟶ 10,625:
<0,7,0>, <1,7,0>, <2,7,9>, <3,7,0>, <4,7,0>, <5,7,8>, <6,7,0>, <7,7,0>, <8,7,0>,
<0,8,0>, <1,8,2>, <2,8,6>, <3,8,4>, <4,8,0>, <5,8,0>, <6,8,7>, <7,8,3>, <8,8,5>
};</
Example
Line 10,682 ⟶ 10,918:
Example of a back-tracking solver, from [[wp:Algorithmics of sudoku]]
{{works with|Ruby|2.0+}}
<
lines = data.lines
9.times.collect { |i| 9.times.collect { |j| lines[i][j].to_i } }
Line 10,772 ⟶ 11,008:
print_matrix(matrix)
puts
print_matrix(solve_sudoku(matrix))</
{{out}}
Line 10,806 ⟶ 11,042:
=={{header|Rust}}==
{{trans|Ada}}
<
fn is_valid(val: u8, x: usize, y: usize, sudoku_ar: &mut Sudoku) -> bool {
Line 10,869 ⟶ 11,105:
println!("Unsolvable");
}
}</
{{out}}
Line 10,891 ⟶ 11,127:
Use CLP solver in SAS/OR:
<
data Indata;
input C1-C9;
Line 10,937 ⟶ 11,173:
/* print solution */
print X;
quit;</
Output:
Line 10,958 ⟶ 11,194:
This solver works with normally 9x9 sudokus as well as with sudokus of jigsaw type or sudokus with additional condition like diagonal constraint.
{{works with|Scala|2.9.1}}
<
class Solver {
Line 11,089 ⟶ 11,325:
println(solution match {case Nil => "no solution!!!" case _ => f2Str(solution)})
}</
{{out}}
<pre>riddle:
Line 11,123 ⟶ 11,359:
The implementation above doesn't work so effective for sudokus like Bracmat version, therefore I implemented a second version inspired by Java section:
{{works with|Scala|2.9.1}}
<
object Solver {
Line 11,240 ⟶ 11,476:
+("\n"*2))
}
}</
{{out}}
<pre>riddle used in Ada section:
Line 11,371 ⟶ 11,607:
The grid should be input in <code>Init_board</code> as a 9x9 matrix. The blanks should be represented by 0. A rule that the initial game should have at least 17 givens is enforced, for it guarantees a unique solution. It is also possible to set a maximum number of steps to the solver using <code>break_point</code>. If it is set to 0, there will be no break until it finds the solution.
<syntaxhighlight lang="text">Init_board=[...
5 3 0 0 7 0 0 0 0;...
6 0 0 1 9 5 0 0 0;...
Line 11,543 ⟶ 11,779:
disp('Invalid solution found.');
disp_board(Solved_board);
end</
{{out}}
Line 11,603 ⟶ 11,839:
=={{header|Sidef}}==
{{trans|Raku}}
<
var (id, im) = i.divmod(9)
var (jd, jm) = j.divmod(9)
Line 11,651 ⟶ 11,887:
)
solve(grid)</
{{out}}
<pre>5 3 9 8 2 4 7 6 1
Line 11,666 ⟶ 11,902:
=={{header|Shale}}==
<
#!/usr/local/bin/shale
Line 12,196 ⟶ 12,432:
// I'd like to see an irregular sudoku with a knight's move constraint. Any takers...
</syntaxhighlight>
'''Output'''
Line 12,237 ⟶ 12,473:
The input and output are presented as strings of 81 characters, where each character is either a digit or a space (indicating an empty cell in the grid). The translation between grids and such strings is trivial (convert grid to string by concatenating rows, reading left to right and then top to bottom), and not covered in the solution. The input is given as a bind variable, ''':game'''.
<
symbols (d) as (select to_char(level) from dual connect by level <= 9)
, board (i) as (select level from dual connect by level <= 81)
Line 12,265 ⟶ 12,501:
from r
where pos = 0
;</
A better (faster) approach - taking advantage of database-specific features - is to create a '''table''' NEIGHBORS (similar to the inline view in the WITH clause) and an index on column I of that table; then the query execution time drops by more than half in most cases.
Line 12,289 ⟶ 12,525:
The example grid given below is taken from [https://en.wikipedia.org/wiki/Sudoku_solving_algorithms Wikipedia]. It does not require any recursive call (it's entirely filled in the first step of ''solve''), as can be seen with additional ''printf'' in the code to follow the algorithm.
<
function sudoku(a) {
s = J(81,20,.)
Line 12,389 ⟶ 12,625:
sudoku(a)
a
end</
'''Output'''
Line 12,410 ⟶ 12,646:
Two more examples, from [http://www.7sudoku.com/very-difficult here] and [http://www.extremesudoku.info/sudoku.html there].
<
.,6,.,5,1,.,.,.,.\
.,.,.,.,.,2,.,.,6\
Line 12,462 ⟶ 12,698:
8 | 3 8 5 4 7 9 2 1 6 |
9 | 7 6 9 3 2 1 4 5 8 |
+-------------------------------------+</
=={{header|Swift}}==
{{trans|Java}}
<
typealias SodukuPuzzle = [[Int]]
Line 12,589 ⟶ 12,825:
let puzzle = Soduku(board: board)
puzzle.solve()
puzzle.printBoard()</
{{out}}
<pre>
Line 12,609 ⟶ 12,845:
{{works with|Swift 3}}
<syntaxhighlight lang="swift">
func solving(board: [[Int]]) -> [[Int]] {
var board = board
Line 12,674 ⟶ 12,910:
print(solving(board: puzzle))
</syntaxhighlight>
{{out}}
<pre>
Line 12,693 ⟶ 12,929:
<
//////////////////////////////////////////////////////////////////////////////
Line 12,823 ⟶ 13,059:
end
endprogram
</syntaxhighlight>
It can be seen that SystemVerilog randomization is a very powerfull tool, in this implementation I directly described the game constraints and the randomization engine takes care of producing solutions, and when multiple solutions are possible they will be chosen at random.
Line 12,878 ⟶ 13,114:
=={{header|Tailspin}}==
There is a blog post about how this code was developed: https://tobega.blogspot.com/2020/05/creating-algorithm.html
<syntaxhighlight lang="tailspin">
templates deduceRemainingDigits
templates findOpenPosition
@:{options: 10"1"};
$ -> \[i;j](when <[]?($::length <..~$@findOpenPosition.options::raw>)> do @findOpenPosition: {row: $i, col: $j, options: ($::length)"1"}; \) -> !VOID
$@ !
end findOpenPosition
templates selectFirst&{pos:}
def digit: $($pos.row;$pos.col) -> $(1);
Line 12,893 ⟶ 13,129:
when <[]?($i <=$pos.row>)
|[]?($j <=$pos.col>)
|[]?(($i::raw-1)~/3 <=($pos.row::raw-1)~/3>)?(($j::raw-1)~/3 <=($pos.col::raw-1)~/3>)> do [$... -> \(when <~=$digit> do $! \)] !
\) !
end selectFirst
@: $;
$ -> findOpenPosition -> #
when <{options: <=0"1">}> do row´1:[] !
when <{options: <=10"1">}> do $@ !
$@ -> selectFirst&{pos: $next} -> deduceRemainingDigits
-> \(when <~=row´1:[]> do @deduceRemainingDigits: $; {options: 10"1"} !
when <=row´1:[]> do ^@deduceRemainingDigits($next.row;$next.col;1)
-> { $next..., options: $next.options
end deduceRemainingDigits
test 'internal solver'
def sample: row´1:[
col´1:[5,3,4,6,7,8,9,1,2],
col´1:[6,7,2,1,9,5,3,4,8],
col´1:[1,9,8,3,4,2,5,6,7],
col´1:[8,5,9,7,6,1,4,2,3],
col´1:[4,2,6,8,5,3,7,9,1],
col´1:[7,1,3,9,2,4,8,5,6],
col´1:[9,6,1,5,3,7,2,8,4],
col´1:[2,8,7,4,1,9,6,3,5],
col´1:[3,4,5,2,8,6,1,7,9]
];
assert $sample -> deduceRemainingDigits <=$sample> 'completed puzzle unchanged'
assert row´1:[
col´1:[[5],3,4,6,7,8,9,1,2],
$sample(row´2..last)...] -> deduceRemainingDigits <=$sample> 'final digit gets placed'
assert row´1:[
col´1:[[],3,4,6,7,8,9,1,2],
$sample(row´2..last)...] -> deduceRemainingDigits <=row´1:[]> 'no remaining options returns empty'
assert row´1:[
col´1:[[5],3,4,6,[2,5,7],8,9,1,[2,5]],
$sample(row´2..last)...] -> deduceRemainingDigits <=$sample> 'solves 3 digits on row'
assert row´1:[
col´1:[5,3,4,6,7,8,9,1,2],
col´1:[[6,7,9],7,2,1,9,5,3,4,8],
col´1:[1,9,8,3,4,2,5,6,7],
col´1:[8,5,9,7,6,1,4,2,3],
col´1:[4,2,6,8,5,3,7,9,1],
col´1:[[7],1,3,9,2,4,8,5,6],
col´1:[[7,9],6,1,5,3,7,2,8,4],
col´1:[2,8,7,4,1,9,6,3,5],
col´1:[3,4,5,2,8,6,1,7,9]
] -> deduceRemainingDigits <=$sample> 'solves 3 digits on column'
assert row´1:[
col´1:[5,3,[4,6],6,7,8,9,1,2],
col´1:[[6],7,2,1,9,5,3,4,8],
col´1:[1,[4,6,9],8,3,4,2,5,6,7],
$sample(row´4..last)...
] -> deduceRemainingDigits <=$sample> 'solves 3 digits in block'
// This gives a contradiction if 3 gets chosen out of [3,5]
assert row´1:[
col´1:[[3,5],[3,4,6],[3,4,6],[3,4,6],7,8,9,1,2],
$sample(row´2..last)...] -> deduceRemainingDigits <=$sample> 'contradiction is backtracked'
end 'internal solver'
composer parseSudoku
row´1:[<section>=3]
rule section: <row>=3 (<'-+'>? <WS>?)
rule row: col´1:[<triple>=3] (<WS>?)
rule triple: <digit|dot>=3 (<'\|'>?)
rule digit: [<'\d'>]
rule dot: <'\.'> -> [1..9 -> '$;']
end parseSudoku
test 'input sudoku'
def parsed:
Line 12,983 ⟶ 13,219:
...|419|..5
...|.8.|.79' -> parseSudoku;
assert $parsed <[<[<[]>=9](9)>=9](9)> 'parsed sudoku has 9 rows containing 9 columns of lists'
assert $parsed(row´1;col´1) <=['5']> 'a digit'
assert $parsed(row´1;col´3) <=['1','2','3','4','5','6','7','8','9']> 'a dot'
end 'input sudoku'
templates solveSudoku
$ -> parseSudoku -> deduceRemainingDigits -> #
when <=row´1:[]> do 'No result found' !
when <> do $ -> \[i](
'$(col´1..col´3)...;|$(col´4..col´6)...;|$(col´7..col´9)...;$#10;' !
$i -> \(when <=row´3|=row´6> do '-----------$#10;' !\) !
\) -> '$...;' !
end solveSudoku
test 'sudoku solver'
assert
Line 13,025 ⟶ 13,261:
'> 'solves sudoku and outputs pretty solution'
end 'sudoku solver'
</syntaxhighlight>
=={{header|Tcl}}==
Line 13,032 ⟶ 13,268:
Note that you can implement more rules if you want. Just make another subclass of <code>Rule</code> and the solver will pick it up and use it automatically.
{{works with|Tcl|8.6}} or {{libheader|TclOO}}
<
oo::class create Sudoku {
variable idata
Line 13,280 ⟶ 13,516:
return 0
}
}</
Demonstration code:
<
sudoku load {
{3 9 4 @ @ 2 6 7 @}
Line 13,305 ⟶ 13,541:
}
}
sudoku destroy</
{{out}}
<pre>+-----+-----+-----+
Line 13,321 ⟶ 13,557:
+-----+-----+-----+</pre>
If we'd added a logger method (after creating the <code>sudoku</code> object but before running the solver) like this:
<
Then this additional logging output would have been produced prior to the result being printed:
<pre>::RuleOnlyChoice solved ::sudoku at 8,0 for 1
Line 13,374 ⟶ 13,610:
Finished solving!</pre>
=={{header|Uiua}}==
{{Works with |Uiua|0.12.0-dev.1}}
Uses experimental '''⮌ orient''' and '''astar''' (only as a lazy way of managing the iteration :-).
<syntaxhighlight lang="uiua">
# Solves Sudoku using brute force.
# Experimental!
S ← [[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]]
Ps ← ⊞⊟.⇡9
Boxes ← ↯∞_9_2 ⊡⊞⊂.0_3_6 ◫3_3Ps
Nines ← ⊂Boxes⊂⟜(⮌1_0)Ps # 27 lists of pos's: one per row, col, box.
IsIn ← ☇1▽:⟜≡(∊:)Nines ¤ # (pos) -> pos's of all peers for a pos.
Peers ← ⊞(IsIn ⊟).⇡9 # For each pos, the pos of every peer (by row, col, box)
Free ← ▽:⟜(¬∊)+1⇡9◴▽⊸(>0)⊡⊡:Peers # Free values at pos (pos board) -> [n]
Next ← (
=/↧.≡(⧻Free) ⊙¤,,⊚=0. # Find most constrained pos.
Free,,⊙◌⊢▽⊙. # Get free values at pos.
≡(⍜⊡⋅∘)λBCa # Generate node for each.
)
End ← =0/+/+=0
astar(⍣Next⋅[]|0|End)S
↙¯1°□⊢⊙◌
</syntaxhighlight>
{{out}}
<pre>
╭─
╷ 8 5 1 3 9 2 4 6 7
╷ 7 2 3 4 6 1 5 8 9
6 9 4 7 5 8 2 3 1
9 6 8 1 4 7 3 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
╯
</pre>
=={{header|Ursala}}==
<
#import nat
Line 13,387 ⟶ 13,668:
~&rgg&& ~&irtPFXlrjrXPS; ~&lrK2tkZ2g&& ~&llrSL2rDrlPrrPljXSPTSL)+-,
//~&p ^|DlrDSLlrlPXrrPDSL(~&,num*+ rep2 block3)*= num block27 ~&iiK0 iota9,
* `0?=\~&iNC ! ~&t digits+-</
test program:
<
example =
Line 13,404 ⟶ 13,685:
010067008
009008000
026400735]-</
{{out}}
<pre>
Line 13,422 ⟶ 13,703:
=={{header|VBA}}==
{{trans|Fortran}}
<
Dim gridSolved(9, 9)
Line 13,523 ⟶ 13,804:
Debug.Print
Next i
End Sub</
{{out}}
<pre>
Line 13,542 ⟶ 13,823:
{{trans|VBA}}
To run in console mode with cscript.
<
Dim gridSolved(9, 9)
Line 13,643 ⟶ 13,924:
End Sub 'Sudoku
Call sudoku</
{{out}}
<pre>Problem:
Line 13,665 ⟶ 13,946:
2 4 3 1 5 7 8 6 9
5 1 9 8 3 6 7 2 4</pre>
===Alternate version===
A faster version adapted from the C solution
<syntaxhighlight lang="vb">
'VBScript Sudoku solver. Fast recursive algorithm adapted from the C version
'It can read a problem passed in the command line or from a file /f:textfile
'if no problem passed it solves a hardwired problem (See the prob0 string)
'problem string can have 0's or dots in the place of unknown values. All chars different from .0123456789 are ignored
Option explicit
Sub print(s):
On Error Resume Next
WScript.stdout.Write (s)
If err= &h80070006& Then WScript.Echo " Please run this script with CScript": WScript.quit
End Sub
function parseprob(s)'problem string to array
Dim i,j,m
print "parsing: " & s & vbCrLf & vbcrlf
j=0
For i=1 To Len(s)
m=Mid(s,i,1)
Select Case m
Case "0","1","2","3","4","5","6","7","8","9"
sdku(j)=cint(m)
j=j+1
Case "."
sdku(j)=0
j=j+1
Case Else 'all other chars are ignored as separators
End Select
Next
' print j
If j<>81 Then parseprob=false Else parseprob=True
End function
sub getprob 'get problem from file or from command line or from
Dim s,s1
With WScript.Arguments.Named
If .exists("f") Then
s1=.item("f")
If InStr(s1,"\")=0 Then s1= Left(WScript.ScriptFullName, InStrRev(WScript.ScriptFullName, "\"))&s1
On Error Resume Next
s= CreateObject("Scripting.FileSystemObject").OpenTextFile (s1, 1).readall
If err Then print "can't open file " & s1 : parseprob(prob0): Exit sub
If parseprob(s) =True Then Exit sub
End if
End With
With WScript.Arguments.Unnamed
If .count<>0 Then
s1=.Item(0)
If parseprob(s1)=True Then exit sub
End if
End With
parseprob(prob0)
End sub
function solve(x,ByVal pos)
'print pos & vbcrlf
'display(x)
Dim row,col,i,j,used
solve=False
If pos=81 Then solve= true :Exit function
row= pos\9
col=pos mod 9
If x(pos) Then solve=solve(x,pos+1):Exit Function
used=0
For i=0 To 8
used=used Or pwr(x(i * 9 + col))
Next
For i=0 To 8
used=used Or pwr(x(row*9 + i))
next
row = (row\ 3) * 3
col = (col \3) * 3
For i=row To row+2
For j=col To col+2
' print i & " " & j &vbcrlf
used = used Or pwr(x(i*9+j))
Next
Next
'print pos & " " & Hex(used) & vbcrlf
For i=1 To 9
If (used And pwr(i))=0 Then
x(pos)=i
'print pos & " " & i & " " & num2bin((used)) & vbcrlf
solve= solve(x,pos+1)
If solve=True Then Exit Function
'x(pos)=0
End If
Next
x(pos)=0
solve=False
End Function
Sub display(x)
Dim i,s
For i=0 To 80
If i mod 9=0 Then print s & vbCrLf :s=""
If i mod 27=0 Then print vbCrLf
If i mod 3=0 Then s=s & " "
s=s& x(i)& " "
Next
print s & vbCrLf
End Sub
Dim pwr:pwr=Array(1,2,4,8,16,32,64,128,256,512,1024,2048)
Dim prob0:prob0= "001005070"&"920600000"& "008000600"&"090020401"& "000000000" & "304080090" & "007000300" & "000007069" & "010800700"
Dim sdku(81),Time
getprob
print "The problem"
display(sdku)
Time=Timer
If solve (sdku,0) Then
print vbcrlf &"solution found" & vbcrlf
display(sdku)
Else
print "no solution found " & vbcrlf
End if
print vbcrlf & "time: " & Timer-Time & " seconds" & vbcrlf
</syntaxhighlight>
{{out}}
<small>
<pre>
parsing: 001005070920600000008000600090020401000000000304080090007000300000007069010800700
The problem
0 0 1 0 0 5 0 7 0
9 2 0 6 0 0 0 0 0
0 0 8 0 0 0 6 0 0
0 9 0 0 2 0 4 0 1
0 0 0 0 0 0 0 0 0
3 0 4 0 8 0 0 9 0
0 0 7 0 0 0 3 0 0
0 0 0 0 0 7 0 6 9
0 1 0 8 0 0 7 0 0
solution found
6 3 1 2 4 5 9 7 8
9 2 5 6 7 8 1 4 3
4 7 8 3 1 9 6 5 2
7 9 6 5 2 3 4 8 1
1 8 2 9 6 4 5 3 7
3 5 4 7 8 1 2 9 6
8 6 7 4 9 2 3 1 5
2 4 3 1 5 7 8 6 9
5 1 9 8 3 6 7 2 4
time: 0.3710938 seconds
</pre>
</small>
=={{header|Wren}}==
{{trans|Kotlin}}
<
construct new(rows) {
if (rows.count != 9 || rows.any { |r| r.count != 9 }) {
Line 13,745 ⟶ 14,184:
"000036040"
]
Sudoku.new(rows).solve()</
{{out}}
Line 13,782 ⟶ 14,221:
can be verified by several other examples.
{{trans|C}}
<
proc Show(X);
Line 13,852 ⟶ 14,291:
..9 ..8 ...
.26 4.. 735 ");
]</
{{out}}
Line 13,871 ⟶ 14,310:
=={{header|zkl}}==
{{trans|C}} Note: Unlike in the C solution, 1<<-1 is defined (as 0).
<
row,col:=pos/9, pos%9;
Line 13,892 ⟶ 14,331:
sdku[pos]=0;
return(False);
}</
<
#<<<
" 5 3 0 0 7 0 0 0 0
Line 13,911 ⟶ 14,350:
s[n*27,27].pump(Console.println,T(Void.Read,8),("| " + "%s%s%s | "*3).fmt); // 3 lines
println("+-----+-----+-----+");
}</
{{out}}
<pre>
|