Sudoku: Difference between revisions
Content added Content deleted
m (→{{header|Tailspin}}: typed array indices) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 12: | Line 12: | ||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="11l">T Sudoku |
||
solved = 0B |
solved = 0B |
||
grid = [0] * 81 |
grid = [0] * 81 |
||
Line 83: | Line 83: | ||
‘000036040’] |
‘000036040’] |
||
Sudoku(rows).solve()</ |
Sudoku(rows).solve()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 118: | Line 118: | ||
=={{header|8th}}== |
=={{header|8th}}== |
||
< |
<syntaxhighlight lang="8th"> |
||
\ |
\ |
||
\ Simple iterative backtracking Sudoku solver for 8th |
\ Simple iterative backtracking Sudoku solver for 8th |
||
Line 265: | Line 265: | ||
"No solution!\n" . |
"No solution!\n" . |
||
then ; |
then ; |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="ada"> |
||
with Ada.Text_IO; |
with Ada.Text_IO; |
||
Line 378: | Line 378: | ||
solve( sudoku_ar ); |
solve( sudoku_ar ); |
||
end Sudoku; |
end Sudoku; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 401: | 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].}} |
{{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''.}} |
{{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''.}} |
||
< |
<syntaxhighlight lang="algol68">MODE AVAIL = [9]BOOL; |
||
MODE BOX = [3, 3]CHAR; |
MODE BOX = [3, 3]CHAR; |
||
Line 495: | Line 495: | ||
"__1__6__9")) |
"__1__6__9")) |
||
END CO |
END CO |
||
)</ |
)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 515: | Line 515: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">#SingleInstance, Force |
||
SetBatchLines, -1 |
SetBatchLines, -1 |
||
SetTitleMatchMode, 3 |
SetTitleMatchMode, 3 |
||
Line 658: | Line 658: | ||
r .= SubStr(p, A_Index, 1) . "|" |
r .= SubStr(p, A_Index, 1) . "|" |
||
return r |
return r |
||
}</ |
}</syntaxhighlight> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f SUDOKU_RC.AWK |
# syntax: GAWK -f SUDOKU_RC.AWK |
||
BEGIN { |
BEGIN { |
||
Line 849: | Line 849: | ||
} |
} |
||
function error(message) { printf("error: %s\n",message) ; errors++ } |
function error(message) { printf("error: %s\n",message) ; errors++ } |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 886: | Line 886: | ||
{{works with|BBC BASIC for Windows}} |
{{works with|BBC BASIC for Windows}} |
||
[[Image:sudoku_bbc.gif|right]] |
[[Image:sudoku_bbc.gif|right]] |
||
< |
<syntaxhighlight lang="bbcbasic"> VDU 23,22,453;453;8,20,16,128 |
||
*FONT Arial,28 |
*FONT Arial,28 |
||
Line 990: | Line 990: | ||
ENDIF |
ENDIF |
||
NEXT |
NEXT |
||
= D%</ |
= D%</syntaxhighlight> |
||
=={{header|BCPL}}== |
=={{header|BCPL}}== |
||
< |
<syntaxhighlight lang="bcpl">// This can be run using Cintcode BCPL freely available from www.cl.cam.ac.uk/users/mr10. |
||
// Implemented by Martin Richards. |
// Implemented by Martin Richards. |
||
Line 1,388: | Line 1,388: | ||
{ count := count + 1 |
{ count := count + 1 |
||
prboard() |
prboard() |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Befunge}}== |
=={{header|Befunge}}== |
||
Line 1,394: | Line 1,394: | ||
Input should be provided as a sequence of 81 digits (optionally separated by whitespace), with zero representing an unknown value. |
Input should be provided as a sequence of 81 digits (optionally separated by whitespace), with zero representing an unknown value. |
||
< |
<syntaxhighlight lang="befunge">99*>1-:0>:#$"0"\# #~`#$_"0"-\::9%:9+00p3/\9/:99++10p3vv%2g\g01< |
||
2%v|:p+9/9\%9:\p\g02\1p\g01\1:p\g00\1:+8:\p02+*93+*3/<>\20g\g#: |
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%\^ |
v<+>:0\`>v >\::9%:9+00p3/\9/:99++10p3/3*+39*+20p\:8+::00g\g2%\^ |
||
Line 1,401: | Line 1,401: | ||
p|<$0.0^!g+:#9/9<^@ ^,>#+5<5_>#!<>#$0"------+-------+-----":#<^ |
p|<$0.0^!g+:#9/9<^@ ^,>#+5<5_>#!<>#$0"------+-------+-----":#<^ |
||
<>v$v1:::0<>"P"`!^>0g#0v#p+9/9\%9:p04:\pg03g021pg03g011pg03g001 |
<>v$v1:::0<>"P"`!^>0g#0v#p+9/9\%9:p04:\pg03g021pg03g011pg03g001 |
||
::>^_:#<0#!:p#-\#1:#g0<>30g010g30g020g30g040g:9%\:9/9+\01-\1+0:</ |
::>^_:#<0#!:p#-\#1:#g0<>30g010g30g020g30g040g:9%\:9/9+\01-\1+0:</syntaxhighlight> |
||
{{in}} |
{{in}} |
||
Line 1,431: | Line 1,431: | ||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
||
The program: |
The program: |
||
< |
<syntaxhighlight lang="bracmat">{sudokuSolver.bra |
||
Solves any 9x9 sudoku, using backtracking. |
Solves any 9x9 sudoku, using backtracking. |
||
Line 1,619: | Line 1,619: | ||
. new$((its.sudoku),!arg):?puzzle |
. new$((its.sudoku),!arg):?puzzle |
||
& (puzzle..Display)$ |
& (puzzle..Display)$ |
||
);</ |
);</syntaxhighlight> |
||
Solve a sudoku that is hard for a brute force solver: |
Solve a sudoku that is hard for a brute force solver: |
||
< |
<syntaxhighlight lang="bracmat">new'( sudokuSolver |
||
, (.- - - - - - - - -) |
, (.- - - - - - - - -) |
||
(.- - - - - 3 - 8 5) |
(.- - - - - 3 - 8 5) |
||
Line 1,631: | Line 1,631: | ||
(.- - 2 - 1 - - - -) |
(.- - 2 - 1 - - - -) |
||
(.- - - - 4 - - - 9) |
(.- - - - 4 - - - 9) |
||
);</ |
);</syntaxhighlight> |
||
Solution: |
Solution: |
||
<pre>|~~~|~~~|~~~| |
<pre>|~~~|~~~|~~~| |
||
Line 1,651: | 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. |
The following code is really only good for size 3 puzzles. A longer, even less readable version [[Sudoku/C|here]] could handle size 4s. |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
void show(int *x) |
void show(int *x) |
||
Line 1,717: | Line 1,717: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
===Backtracking=== |
===Backtracking=== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
class SudokuSolver |
class SudokuSolver |
||
Line 1,824: | Line 1,824: | ||
Console.Read(); |
Console.Read(); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=== Best First Search=== |
=== Best First Search=== |
||
<!-- By Martin Freedman, 20/11/2021 --> |
<!-- By Martin Freedman, 20/11/2021 --> |
||
< |
<syntaxhighlight lang="csharp">using System.Linq; |
||
using static System.Linq.Enumerable; |
using static System.Linq.Enumerable; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
Line 1,904: | Line 1,904: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Usage |
Usage |
||
< |
<syntaxhighlight lang="csharp">using System.Linq; |
||
using static System.Linq.Enumerable; |
using static System.Linq.Enumerable; |
||
using static System.Console; |
using static System.Console; |
||
Line 1,941: | Line 1,941: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Output |
Output |
||
<pre>693784512 |
<pre>693784512 |
||
Line 1,960: | Line 1,960: | ||
{{libheader|Microsoft Solver Foundation}} |
{{libheader|Microsoft Solver Foundation}} |
||
<!-- By Nigel Galloway, Jan 29, 2012 --> |
<!-- By Nigel Galloway, Jan 29, 2012 --> |
||
< |
<syntaxhighlight lang="csharp">using Microsoft.SolverFoundation.Solvers; |
||
namespace Sudoku |
namespace Sudoku |
||
Line 2,032: | Line 2,032: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Produces: |
Produces: |
||
<pre> |
<pre> |
||
Line 2,049: | Line 2,049: | ||
==="Dancing Links"/Algorithm X=== |
==="Dancing Links"/Algorithm X=== |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
using System.Text; |
using System.Text; |
||
Line 2,327: | Line 2,327: | ||
public static string DelimitWith<T>(this IEnumerable<T> source, string separator) => string.Join(separator, source); |
public static string DelimitWith<T>(this IEnumerable<T> source, string separator) => string.Join(separator, source); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,352: | Line 2,352: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="cpp">#include <iostream> |
||
using namespace std; |
using namespace std; |
||
Line 2,443: | Line 2,443: | ||
ss.solve(); |
ss.solve(); |
||
return EXIT_SUCCESS; |
return EXIT_SUCCESS; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
< |
<syntaxhighlight lang="clojure">(ns rosettacode.sudoku |
||
(:use [clojure.pprint :only (cl-format)])) |
(:use [clojure.pprint :only (cl-format)])) |
||
Line 2,469: | Line 2,469: | ||
(if (= x (dec c)) |
(if (= x (dec c)) |
||
(recur ng 0 (inc y)) |
(recur ng 0 (inc y)) |
||
(recur ng (inc x) y)))))))</ |
(recur ng (inc x) y)))))))</syntaxhighlight> |
||
< |
<syntaxhighlight lang="clojure">sudoku>(cl-format true "~{~{~a~^ ~}~%~}" |
||
(solve [[3 9 4 0 0 2 6 7 0] |
(solve [[3 9 4 0 0 2 6 7 0] |
||
[0 0 0 3 0 0 4 0 0] |
[0 0 0 3 0 0 4 0 0] |
||
Line 2,491: | Line 2,491: | ||
8 2 6 4 1 9 7 3 5 |
8 2 6 4 1 9 7 3 5 |
||
nil</ |
nil</syntaxhighlight> |
||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
A simple solver without optimizations (except for pre-computing the possible entries of a cell). |
A simple solver without optimizations (except for pre-computing the possible entries of a cell). |
||
< |
<syntaxhighlight lang="lisp">(defun row-neighbors (row column grid &aux (neighbors '())) |
||
(dotimes (i 9 neighbors) |
(dotimes (i 9 neighbors) |
||
(let ((x (aref grid row i))) |
(let ((x (aref grid row i))) |
||
Line 2,534: | Line 2,534: | ||
(setf (aref grid row column) choice) |
(setf (aref grid row column) choice) |
||
(when (eq grid (solve grid row (1+ column))) |
(when (eq grid (solve grid row (1+ column))) |
||
(return grid))))))</ |
(return grid))))))</syntaxhighlight> |
||
Example: |
Example: |
||
<pre>> (defparameter *puzzle* |
<pre>> (defparameter *puzzle* |
||
Line 2,564: | 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...]". |
Based on the Java implementation presented in the video "[https://www.youtube.com/watch?v=mcXc8Mva2bA Create a Sudoku Solver In Java...]". |
||
< |
<syntaxhighlight lang="ruby">GRID_SIZE = 9 |
||
def isNumberInRow(board, number, row) |
def isNumberInRow(board, number, row) |
||
Line 2,637: | Line 2,637: | ||
printBoard(board) |
printBoard(board) |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,666: | Line 2,666: | ||
=={{header|Curry}}== |
=={{header|Curry}}== |
||
Copied from [http://www.informatik.uni-kiel.de/~curry/examples/ Curry: Example Programs]. |
Copied from [http://www.informatik.uni-kiel.de/~curry/examples/ Curry: Example Programs]. |
||
< |
<syntaxhighlight lang="curry">----------------------------------------------------------------------------- |
||
--- Solving Su Doku puzzles in Curry with FD constraints |
--- Solving Su Doku puzzles in Curry with FD constraints |
||
--- |
--- |
||
Line 2,728: | Line 2,728: | ||
" 5 7 921 ", |
" 5 7 921 ", |
||
" 64 9 ", |
" 64 9 ", |
||
" 2 438"]</ |
" 2 438"]</syntaxhighlight> |
||
Line 2,734: | Line 2,734: | ||
{{Works with|PAKCS}} |
{{Works with|PAKCS}} |
||
Minimal w/o read or show utilities. |
Minimal w/o read or show utilities. |
||
< |
<syntaxhighlight lang="curry">import CLPFD |
||
import Constraint (allC) |
import Constraint (allC) |
||
import List (transpose) |
import List (transpose) |
||
Line 2,767: | Line 2,767: | ||
, [7,_,_,6,_,_,5,_,_] |
, [7,_,_,6,_,_,5,_,_] |
||
] |
] |
||
main | sudoku xs = xs where xs = test</ |
main | sudoku xs = xs where xs = test</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Execution time: 0 msec. / elapsed: 10 msec. |
<pre>Execution time: 0 msec. / elapsed: 10 msec. |
||
Line 2,775: | Line 2,775: | ||
{{trans|C++}} |
{{trans|C++}} |
||
A little over-engineered solution, that shows some strong static typing useful in larger programs. |
A little over-engineered solution, that shows some strong static typing useful in larger programs. |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.range, std.string, std.algorithm, std.array, |
||
std.ascii, std.typecons; |
std.ascii, std.typecons; |
||
Line 2,901: | Line 2,901: | ||
else |
else |
||
solution.get.representSudoku.writeln; |
solution.get.representSudoku.writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>8 5 . | . . 2 | 4 . . |
<pre>8 5 . | . . 2 | 4 . . |
||
Line 2,929: | Line 2,929: | ||
===Short Version=== |
===Short Version=== |
||
Adapted from: http://code.activestate.com/recipes/576725-brute-force-sudoku-solver/ |
Adapted from: http://code.activestate.com/recipes/576725-brute-force-sudoku-solver/ |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.range; |
||
const(int)[] solve(immutable int[] s) pure nothrow @safe { |
const(int)[] solve(immutable int[] s) pure nothrow @safe { |
||
Line 2,962: | Line 2,962: | ||
0, 0, 0, 0, 3, 6, 0, 4, 0]; |
0, 0, 0, 0, 3, 6, 0, 4, 0]; |
||
writefln("%(%s\n%)", problem.solve.chunks(9)); |
writefln("%(%s\n%)", problem.solve.chunks(9)); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[8, 5, 9, 6, 1, 2, 4, 3, 7] |
<pre>[8, 5, 9, 6, 1, 2, 4, 3, 7] |
||
Line 2,976: | Line 2,976: | ||
===No-Heap Version=== |
===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. |
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. |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.range, std.typecons; |
||
Nullable!(const ubyte[81]) solve(in ubyte[81] s) pure nothrow @safe @nogc { |
Nullable!(const ubyte[81]) solve(in ubyte[81] s) pure nothrow @safe @nogc { |
||
Line 3,017: | Line 3,017: | ||
0, 0, 0, 0, 3, 6, 0, 4, 0]; |
0, 0, 0, 0, 3, 6, 0, 4, 0]; |
||
writefln("%(%s\n%)", problem.solve.get[].chunks(9)); |
writefln("%(%s\n%)", problem.solve.get[].chunks(9)); |
||
}</ |
}</syntaxhighlight> |
||
Same output. |
Same output. |
||
=={{header|Delphi}}== |
=={{header|Delphi}}== |
||
Example taken from C++ |
Example taken from C++ |
||
< |
<syntaxhighlight lang="delphi">type |
||
TIntArray = array of Integer; |
TIntArray = array of Integer; |
||
Line 3,146: | Line 3,146: | ||
ShowMessage('Solved!'); |
ShowMessage('Solved!'); |
||
end; |
end; |
||
end;</ |
end;</syntaxhighlight> |
||
Usage: |
Usage: |
||
< |
<syntaxhighlight lang="delphi">var |
||
SudokuSolver: TSudokuSolver; |
SudokuSolver: TSudokuSolver; |
||
begin |
begin |
||
Line 3,165: | Line 3,165: | ||
FreeAndNil(SudokuSolver); |
FreeAndNil(SudokuSolver); |
||
end; |
end; |
||
end;</ |
end;</syntaxhighlight> |
||
=={{header|EasyLang}}== |
=={{header|EasyLang}}== |
||
<lang>len row[] 810 |
<syntaxhighlight lang="text">len row[] 810 |
||
len col[] 810 |
len col[] 810 |
||
len box[] 810 |
len box[] 810 |
||
Line 3,245: | Line 3,245: | ||
0 0 0 0 3 0 5 0 6 |
0 0 0 0 3 0 5 0 6 |
||
9 6 0 0 1 0 3 0 0 |
9 6 0 0 1 0 3 0 0 |
||
0 5 0 6 9 0 0 1 0</ |
0 5 0 6 9 0 0 1 0</syntaxhighlight> |
||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
{{trans|Erlang}} |
{{trans|Erlang}} |
||
< |
<syntaxhighlight lang="elixir">defmodule Sudoku do |
||
def display( grid ), do: ( for y <- 1..9, do: display_row(y, grid) ) |
def display( grid ), do: ( for y <- 1..9, do: display_row(y, grid) ) |
||
Line 3,405: | Line 3,405: | ||
{{3, 8}, 2}, {{5, 8}, 1}, |
{{3, 8}, 2}, {{5, 8}, 1}, |
||
{{5, 9}, 4}, {{9, 9}, 9}] |
{{5, 9}, 4}, {{9, 9}, 9}] |
||
Sudoku.task( difficult )</ |
Sudoku.task( difficult )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,465: | Line 3,465: | ||
=={{header|Erlang}}== |
=={{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. |
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"> |
|||
<lang Erlang> |
|||
-module( sudoku ). |
-module( sudoku ). |
||
Line 3,628: | Line 3,628: | ||
display( Solved ), |
display( Solved ), |
||
io:nl(). |
io:nl(). |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,712: | Line 3,712: | ||
0 is the empty cell. |
0 is the empty cell. |
||
<syntaxhighlight lang="erre"> |
|||
<lang ERRE> |
|||
!-------------------------------------------------------------------- |
!-------------------------------------------------------------------- |
||
! risolve Sudoku: in input il file SUDOKU.TXT |
! risolve Sudoku: in input il file SUDOKU.TXT |
||
Line 4,119: | Line 4,119: | ||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
===Backtracking=== |
===Backtracking=== |
||
<!-- By Martin Freedman, 26/11/2021 --> |
<!-- By Martin Freedman, 26/11/2021 --> |
||
< |
<syntaxhighlight lang="fsharp">module SudokuBacktrack |
||
//Helpers |
//Helpers |
||
Line 4,197: | Line 4,197: | ||
/// solve sudoku using simple backtracking |
/// solve sudoku using simple backtracking |
||
let solve grid = grid |> parseGrid >>= flip backtracker (Some "A1")</ |
let solve grid = grid |> parseGrid >>= flip backtracker (Some "A1")</syntaxhighlight> |
||
'''Usage:''' |
'''Usage:''' |
||
< |
<syntaxhighlight lang="fsharp">open System |
||
open SudokuBacktrack |
open SudokuBacktrack |
||
Line 4,211: | Line 4,211: | ||
printfn "Press any key to exit" |
printfn "Press any key to exit" |
||
Console.ReadKey() |> ignore |
Console.ReadKey() |> ignore |
||
0</ |
0</syntaxhighlight> |
||
{{Output}}<pre> |
{{Output}}<pre> |
||
Puzzle: |
Puzzle: |
||
Line 4,240: | Line 4,240: | ||
===Constraint Satisfaction (Norvig)=== |
===Constraint Satisfaction (Norvig)=== |
||
<!-- By Martin Freedman, 27/11/2021 --> |
<!-- By Martin Freedman, 27/11/2021 --> |
||
< |
<syntaxhighlight lang="fsharp">// https://norvig.com/sudoku.html |
||
// using array O(1) lookup & mutable instead of map O(logn) immutable - now 6 times faster |
// using array O(1) lookup & mutable instead of map O(logn) immutable - now 6 times faster |
||
module SudokuCPSArray |
module SudokuCPSArray |
||
Line 4,364: | Line 4,364: | ||
let solveNoSearch: string -> string = solver applyCPS |
let solveNoSearch: string -> string = solver applyCPS |
||
let solveWithSearch: string -> string = solver (applyCPS >> (Option.bind search)) |
let solveWithSearch: string -> string = solver (applyCPS >> (Option.bind search)) |
||
let solveWithSearchToMapOnly:string -> int[][] option = run None id (applyCPS >> (Option.bind search)) </ |
let solveWithSearchToMapOnly:string -> int[][] option = run None id (applyCPS >> (Option.bind search)) </syntaxhighlight> |
||
'''Usage'''< |
'''Usage'''<syntaxhighlight lang="fsharp">open System |
||
open SudokuCPSArray |
open SudokuCPSArray |
||
open System.Diagnostics |
open System.Diagnostics |
||
Line 4,412: | Line 4,412: | ||
printfn "Some sudoku17 puzzles failed" |
printfn "Some sudoku17 puzzles failed" |
||
Console.ReadKey() |> ignore |
Console.ReadKey() |> ignore |
||
0</ |
0</syntaxhighlight> |
||
{{Output}}Timings run on i7500U @2.75Ghz CPU, 16GB RAM<pre>Easy board solution automatic with constraint propagation |
{{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 |
4 8 3 |9 2 1 |6 5 7 |
||
Line 4,472: | Line 4,472: | ||
===SLPsolve=== |
===SLPsolve=== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Solve Sudoku Like Puzzles. Nigel Galloway: September 6th., 2018 |
// 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)] |
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: | Line 4,501: | ||
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.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 "") |
|>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> |
|||
</lang> |
|||
'''Usage:''' |
'''Usage:''' |
||
Given sud1.csv: |
Given sud1.csv: |
||
Line 4,516: | Line 4,516: | ||
</pre> |
</pre> |
||
then |
then |
||
< |
<syntaxhighlight lang="fsharp"> |
||
let n=SLPsolve (fE ([1..9]|>List.map(string)) 9 3 3 "sud1.csv") |
let n=SLPsolve (fE ([1..9]|>List.map(string)) 9 3 3 "sud1.csv") |
||
printSLP ([1..9]|>List.map(string)) (Seq.item 0 n) |
printSLP ([1..9]|>List.map(string)) (Seq.item 0 n) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,535: | Line 4,535: | ||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
{{works with|4tH|3.60.0}} |
{{works with|4tH|3.60.0}} |
||
< |
<syntaxhighlight lang="forth">include lib/interprt.4th |
||
include lib/istype.4th |
include lib/istype.4th |
||
include lib/argopen.4th |
include lib/argopen.4th |
||
Line 4,898: | Line 4,898: | ||
; |
; |
||
sudoku</ |
sudoku</syntaxhighlight> |
||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
{{works with|Fortran|90 and later}} |
{{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. |
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. |
||
< |
<syntaxhighlight lang="fortran">program sudoku |
||
implicit none |
implicit none |
||
Line 5,000: | Line 5,000: | ||
end subroutine pretty_print |
end subroutine pretty_print |
||
end program sudoku</ |
end program sudoku</syntaxhighlight> |
||
{{out}}<pre> |
{{out}}<pre> |
||
+-----+-----+-----+ |
+-----+-----+-----+ |
||
Line 5,033: | Line 5,033: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
{{trans|VBA}} |
{{trans|VBA}} |
||
< |
<syntaxhighlight lang="freebasic">Dim Shared As Integer cuadricula(9, 9), cuadriculaResuelta(9, 9) |
||
Function isSafe(i As Integer, j As Integer, n As Integer) As Boolean |
Function isSafe(i As Integer, j As Integer, n As Integer) As Boolean |
||
Line 5,119: | Line 5,119: | ||
If (i Mod 3 = 0) Then Print !"\n---------+---------+---------" Else Print |
If (i Mod 3 = 0) Then Print !"\n---------+---------+---------" Else Print |
||
Next i |
Next i |
||
Sleep</ |
Sleep</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 5,141: | Line 5,141: | ||
=={{header|FutureBasic}}== |
=={{header|FutureBasic}}== |
||
First is a short version: |
First is a short version: |
||
< |
<syntaxhighlight lang="futurebasic"> |
||
include "ConsoleWindow" |
include "ConsoleWindow" |
||
include "NSLog.incl" |
include "NSLog.incl" |
||
Line 5,250: | Line 5,250: | ||
print "No solution found" |
print "No solution found" |
||
end if |
end if |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
Line 5,712: | Line 5,712: | ||
Input to function solve is an 81 character string. |
Input to function solve is an 81 character string. |
||
This seems to be a conventional computer representation for Sudoku puzzles. |
This seems to be a conventional computer representation for Sudoku puzzles. |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 5,913: | Line 5,913: | ||
} |
} |
||
c.r.l, c.l.r = &c.x, &c.x |
c.r.l, c.l.r = &c.x, &c.x |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 5,946: | Line 5,946: | ||
Imprime todas las soluciones posibles, sale con un error, pero funciona. |
Imprime todas las soluciones posibles, sale con un error, pero funciona. |
||
< |
<syntaxhighlight lang="golfscript"> |
||
'Solution:' |
'Solution:' |
||
;'2 8 4 3 7 5 1 6 9 |
;'2 8 4 3 7 5 1 6 9 |
||
Line 5,960: | Line 5,960: | ||
~]{:@0?:^~!{@p}*10,@9/^9/=-@^9%>9%-@3/^9%3/>3%3/^27/={+}*-{@^<\+@1^+>+}/1}do |
~]{:@0?:^~!{@p}*10,@9/^9/=-@^9%>9%-@3/^9%3/>3%3/^27/={+}*-{@^<\+@1^+>+}/1}do |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
Line 5,968: | Line 5,968: | ||
I consider this a "brute force" solution of sorts, in that it is the same method I use when solving Sudokus manually. |
I consider this a "brute force" solution of sorts, in that it is the same method I use when solving Sudokus manually. |
||
< |
<syntaxhighlight lang="groovy">final CELL_VALUES = ('1'..'9') |
||
class GridException extends Exception { |
class GridException extends Exception { |
||
Line 6,035: | Line 6,035: | ||
} |
} |
||
grid |
grid |
||
}</ |
}</syntaxhighlight> |
||
'''Test/Benchmark Cases''' |
'''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]] |
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]] |
||
< |
<syntaxhighlight lang="groovy">def sudokus = [ |
||
//Used in Curry solution: ~ 0.1 seconds |
//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', |
'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: | Line 6,102: | ||
solution.each { println it } |
solution.each { println it } |
||
println "\nELAPSED: ${elapsed} seconds" |
println "\nELAPSED: ${elapsed} seconds" |
||
}</ |
}</syntaxhighlight> |
||
{{out}} (last only): |
{{out}} (last only): |
||
Line 6,136: | Line 6,136: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang="java">public class Sudoku |
||
{ |
{ |
||
private int mBoard[][]; |
private int mBoard[][]; |
||
Line 6,254: | Line 6,254: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 6,293: | Line 6,293: | ||
====ES6==== |
====ES6==== |
||
< |
<syntaxhighlight lang="javascript">//-------------------------------------------[ Dancing Links and Algorithm X ]-- |
||
/** |
/** |
||
* The doubly-doubly circularly linked data object. |
* The doubly-doubly circularly linked data object. |
||
Line 6,566: | Line 6,566: | ||
search(H, []); |
search(H, []); |
||
}; |
}; |
||
</syntaxhighlight> |
|||
</lang> |
|||
<syntaxhighlight lang="javascript">[ |
|||
<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', |
'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.', |
'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: | Line 6,593: | ||
let s = new Array(Math.pow(n, 4)).fill('.').join(''); |
let s = new Array(Math.pow(n, 4)).fill('.').join(''); |
||
reduceGrid(s); |
reduceGrid(s); |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre>+-------+-------+-------+ |
<pre>+-------+-------+-------+ |
||
Line 6,625: | Line 6,625: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">function check(i, j) |
||
id, im = div(i, 9), mod(i, 9) |
id, im = div(i, 9), mod(i, 9) |
||
jd, jm = div(j, 9), mod(j, 9) |
jd, jm = div(j, 9), mod(j, 9) |
||
Line 6,691: | Line 6,691: | ||
0, 5, 0, 6, 9, 0, 0, 1, 0] |
0, 5, 0, 6, 9, 0, 0, 1, 0] |
||
solve_sudoku(display, grid)</ |
solve_sudoku(display, grid)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 6,709: | Line 6,709: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="scala">// version 1.2.10 |
||
class Sudoku(rows: List<String>) { |
class Sudoku(rows: List<String>) { |
||
Line 6,792: | Line 6,792: | ||
) |
) |
||
Sudoku(rows).solve() |
Sudoku(rows).solve() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 6,827: | Line 6,827: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
===without FFI, slow=== |
===without FFI, slow=== |
||
< |
<syntaxhighlight lang="lua">--9x9 sudoku solver in lua |
||
--based on a branch and bound solution |
--based on a branch and bound solution |
||
--fields are not tried in plain order |
--fields are not tried in plain order |
||
Line 7,009: | Line 7,009: | ||
if x then |
if x then |
||
return printer(x) |
return printer(x) |
||
end</ |
end</syntaxhighlight> |
||
Input: |
Input: |
||
<pre> |
<pre> |
||
Line 7,041: | Line 7,041: | ||
Time with luajit: 9.245s |
Time with luajit: 9.245s |
||
===with FFI, fast=== |
===with FFI, fast=== |
||
< |
<syntaxhighlight lang="lua">#!/usr/bin/env luajit |
||
ffi=require"ffi" |
ffi=require"ffi" |
||
local printf=function(fmt, ...) io.write(string.format(fmt, ...)) end |
local printf=function(fmt, ...) io.write(string.format(fmt, ...)) end |
||
Line 7,109: | Line 7,109: | ||
... .8. .79 |
... .8. .79 |
||
]]) |
]]) |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>> time ./sudoku_fast.lua |
<pre>> time ./sudoku_fast.lua |
||
Line 7,128: | Line 7,128: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">solve[sudoku_] := |
||
NestWhile[ |
NestWhile[ |
||
Join @@ Table[ |
Join @@ Table[ |
||
Line 7,137: | Line 7,137: | ||
Extract[Partition[s, {3, 3}], Quotient[#, 3, -2]]]} & /@ |
Extract[Partition[s, {3, 3}], Quotient[#, 3, -2]]]} & /@ |
||
Position[s, 0, {2}], |
Position[s, 0, {2}], |
||
Length@Last@# &], {s, #}] &, {sudoku}, ! FreeQ[#, 0] &]</ |
Length@Last@# &], {s, #}] &, {sudoku}, ! FreeQ[#, 0] &]</syntaxhighlight> |
||
Example: |
Example: |
||
<lang>solve[{{9, 7, 0, 3, 0, 0, 0, 6, 0}, |
<syntaxhighlight lang="text">solve[{{9, 7, 0, 3, 0, 0, 0, 6, 0}, |
||
{0, 6, 0, 7, 5, 0, 0, 0, 0}, |
{0, 6, 0, 7, 5, 0, 0, 0, 0}, |
||
{0, 0, 0, 0, 0, 8, 0, 5, 0}, |
{0, 0, 0, 0, 0, 8, 0, 5, 0}, |
||
Line 7,147: | Line 7,147: | ||
{7, 0, 0, 0, 2, 5, 0, 0, 0}, |
{7, 0, 0, 0, 2, 5, 0, 0, 0}, |
||
{0, 0, 2, 0, 1, 0, 0, 0, 8}, |
{0, 0, 2, 0, 1, 0, 0, 0, 8}, |
||
{0, 4, 0, 0, 0, 7, 3, 0, 0}}]</ |
{0, 4, 0, 0, 0, 7, 3, 0, 0}}]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{{{9, 7, 5, 3, 4, 2, 8, 6, 1}, {8, 6, 1, 7, 5, 9, 4, 3, 2}, {3, 2, 4, |
<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: | Line 7,158: | ||
For this to work, this code must be placed in a file named "sudokuSolver.m" |
For this to work, this code must be placed in a file named "sudokuSolver.m" |
||
< |
<syntaxhighlight lang="matlab">function solution = sudokuSolver(sudokuGrid) |
||
%Define what each of the sub-boxes of the sudoku grid are by defining |
%Define what each of the sub-boxes of the sudoku grid are by defining |
||
Line 7,510: | Line 7,510: | ||
%% End of program |
%% End of program |
||
end %end sudokuSolver</ |
end %end sudokuSolver</syntaxhighlight> |
||
[http://www.menneske.no/sudoku/eng/showpuzzle.html?number=6903541 Test Input]: |
[http://www.menneske.no/sudoku/eng/showpuzzle.html?number=6903541 Test Input]: |
||
All empty cells must have a value of NaN. |
All empty cells must have a value of NaN. |
||
< |
<syntaxhighlight lang="matlab">sudoku = [NaN NaN NaN NaN 8 3 9 NaN NaN |
||
1 NaN NaN NaN NaN NaN NaN 3 NaN |
1 NaN NaN NaN NaN NaN NaN 3 NaN |
||
NaN NaN 4 NaN NaN NaN NaN 7 NaN |
NaN NaN 4 NaN NaN NaN NaN 7 NaN |
||
Line 7,521: | Line 7,521: | ||
NaN 2 NaN NaN NaN NaN NaN NaN NaN |
NaN 2 NaN NaN NaN NaN NaN NaN NaN |
||
NaN 8 NaN NaN NaN 9 2 NaN NaN |
NaN 8 NaN NaN NaN 9 2 NaN NaN |
||
NaN NaN NaN 2 5 NaN NaN NaN 6]</ |
NaN NaN NaN 2 5 NaN NaN NaN 6]</syntaxhighlight> |
||
[http://www.menneske.no/sudoku/eng/solution.html?number=6903541 Output]: |
[http://www.menneske.no/sudoku/eng/solution.html?number=6903541 Output]: |
||
< |
<syntaxhighlight lang="matlab">solution = |
||
7 6 5 4 8 3 9 2 1 |
7 6 5 4 8 3 9 2 1 |
||
Line 7,533: | Line 7,533: | ||
9 2 6 1 4 7 5 8 3 |
9 2 6 1 4 7 5 8 3 |
||
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</ |
4 7 3 2 5 8 1 9 6</syntaxhighlight> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="nim">{.this: self.} |
||
type |
type |
||
Line 7,611: | Line 7,611: | ||
var puzzle = Sudoku() |
var puzzle = Sudoku() |
||
puzzle.init(rows) |
puzzle.init(rows) |
||
puzzle.solve()</ |
puzzle.solve()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 7,644: | Line 7,644: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
uses the library [http://ocamlgraph.lri.fr/index.en.html ocamlgraph] |
uses the library [http://ocamlgraph.lri.fr/index.en.html ocamlgraph] |
||
< |
<syntaxhighlight lang="ocaml">(* Ocamlgraph demo program: solving the Sudoku puzzle using graph coloring |
||
Copyright 2004-2007 Sylvain Conchon, Jean-Christophe Filliatre, Julien Signoles |
Copyright 2004-2007 Sylvain Conchon, Jean-Christophe Filliatre, Julien Signoles |
||
Line 7,713: | Line 7,713: | ||
module C = Coloring.Mark(G) |
module C = Coloring.Mark(G) |
||
let () = C.coloring g 9; display ()</ |
let () = C.coloring g 9; display ()</syntaxhighlight> |
||
=={{header|Oz}}== |
=={{header|Oz}}== |
||
Using built-in constraint propagation and search. |
Using built-in constraint propagation and search. |
||
< |
<syntaxhighlight lang="oz">declare |
||
%% a puzzle is a function that returns an initial board configuration |
%% a puzzle is a function that returns an initial board configuration |
||
fun {Puzzle1} |
fun {Puzzle1} |
||
Line 7,800: | Line 7,800: | ||
end |
end |
||
in |
in |
||
{Inspect {Solve Puzzle1}.1}</ |
{Inspect {Solve Puzzle1}.1}</syntaxhighlight> |
||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
Build plugin for PARI's function interface from C code: sudoku.c |
Build plugin for PARI's function interface from C code: sudoku.c |
||
< |
<syntaxhighlight lang="c">#include <pari/pari.h> |
||
typedef int SUDOKU [9][9]; |
typedef int SUDOKU [9][9]; |
||
Line 7,875: | Line 7,875: | ||
return gen_0; /* no solution */ |
return gen_0; /* no solution */ |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Compile plugin: gcc -O2 -Wall -fPIC -shared sudoku.c -o libsudoku.so -lpari |
Compile plugin: gcc -O2 -Wall -fPIC -shared sudoku.c -o libsudoku.so -lpari |
||
Install plugin from home directory and play: |
Install plugin from home directory and play: |
||
< |
<syntaxhighlight lang="parigp">install("plug_sudoku", "G", "sudoku", "~/libsudoku.so")</syntaxhighlight> |
||
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] |
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: | Line 7,907: | ||
{{works with|Free Pascal}} |
{{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. |
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. |
||
< |
<syntaxhighlight lang="pascal">Program soduko; |
||
{$IFDEF FPC} |
{$IFDEF FPC} |
||
{$CODEALIGN proc=16,loop=8} |
{$CODEALIGN proc=16,loop=8} |
||
Line 8,163: | Line 8,163: | ||
Outfield(solF); |
Outfield(solF); |
||
writeln(86400*1000*(T1-T0)/k:10:3,' ms Test calls :',callCnt/k:8:0); |
writeln(86400*1000*(T1-T0)/k:10:3,' ms Test calls :',callCnt/k:8:0); |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 8,199: | Line 8,199: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">#!/usr/bin/perl |
||
use integer; |
use integer; |
||
use strict; |
use strict; |
||
Line 8,238: | Line 8,238: | ||
} |
} |
||
} |
} |
||
solve();</ |
solve();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 8,256: | Line 8,256: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Simple brute force solution. Generally quite good but will struggle on some puzzles (eg see "the beast" below) |
Simple brute force solution. Generally quite good but will struggle on some puzzles (eg see "the beast" below) |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<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;">""" |
<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: | Line 8,308: | ||
<span style="color: #000000;">brute_solve</span><span style="color: #0000FF;">()</span> |
<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> |
<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> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 8,326: | Line 8,326: | ||
contains 339 puzzles, can be run as a command-line or gui program, check for multiple solutions, and produce |
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). |
a more readable single-puzzle output (example below). |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<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 |
<span style="color: #000080;font-style:italic;">-- Working directly on 81-character strings ultimately proves easier: Originally I |
||
Line 8,970: | Line 8,970: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
||
<span style="color: #000000;">test</span><span style="color: #0000FF;">()</span> |
<span style="color: #000000;">test</span><span style="color: #0000FF;">()</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 9,039: | Line 9,039: | ||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="php"> class SudokuSolver { |
||
protected $grid = []; |
protected $grid = []; |
||
protected $emptySymbol; |
protected $emptySymbol; |
||
Line 9,163: | Line 9,163: | ||
$solver = new SudokuSolver('009170000020600001800200000200006053000051009005040080040000700006000320700003900'); |
$solver = new SudokuSolver('009170000020600001800200000200006053000051009005040080040000700006000320700003900'); |
||
$solver->solve(); |
$solver->solve(); |
||
$solver->display();</ |
$solver->display();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 9,183: | Line 9,183: | ||
Using constraint programming. |
Using constraint programming. |
||
< |
<syntaxhighlight lang="picat">import util. |
||
import cp. |
import cp. |
||
Line 9,253: | Line 9,253: | ||
"....839..1......3...4....7..42.3....6.......4....7..1..2........8...92.....25...6", |
"....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.." |
"..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686........7..6..5.." |
||
].</ |
].</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 9,285: | Line 9,285: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(load "lib/simul.l") |
||
### Fields/Board ### |
### Fields/Board ### |
||
Line 9,366: | Line 9,366: | ||
(0 6 0 0 0 0 2 8 0) |
(0 6 0 0 0 0 2 8 0) |
||
(0 0 0 4 1 9 0 0 5) |
(0 0 0 4 1 9 0 0 5) |
||
(0 0 0 0 8 0 0 7 9) ) )</ |
(0 0 0 0 8 0 0 7 9) ) )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> +---+---+---+---+---+---+---+---+---+ |
<pre> +---+---+---+---+---+---+---+---+---+ |
||
Line 9,388: | Line 9,388: | ||
+---+---+---+---+---+---+---+---+---+ |
+---+---+---+---+---+---+---+---+---+ |
||
a b c d e f g h i</pre> |
a b c d e f g h i</pre> |
||
<lang |
<syntaxhighlight lang="picolisp">(go)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> +---+---+---+---+---+---+---+---+---+ |
<pre> +---+---+---+---+---+---+---+---+---+ |
||
Line 9,413: | Line 9,413: | ||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
Working PL/I version, derived from the Rosetta Fortran version. |
Working PL/I version, derived from the Rosetta Fortran version. |
||
< |
<syntaxhighlight lang="pli">sudoku: procedure options (main); /* 27 July 2014 */ |
||
declare grid (9,9) fixed (1) static initial ( |
declare grid (9,9) fixed (1) static initial ( |
||
Line 9,496: | Line 9,496: | ||
end sudoku; |
end sudoku; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 9,530: | Line 9,530: | ||
Another PL/I version, reads sudoku from the text data file as 81 character record. |
Another PL/I version, reads sudoku from the text data file as 81 character record. |
||
< |
<syntaxhighlight lang="pli"> |
||
*PROCESS MARGINS(1,120) LIBS(SINGLE,STATIC); |
*PROCESS MARGINS(1,120) LIBS(SINGLE,STATIC); |
||
*PROCESS OPTIMIZE(2) DFT(REORDER); |
*PROCESS OPTIMIZE(2) DFT(REORDER); |
||
Line 9,669: | Line 9,669: | ||
end sudoku; |
end sudoku; |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
< |
<syntaxhighlight lang="prolog">:- use_module(library(clpfd)). |
||
sudoku(Rows) :- |
sudoku(Rows) :- |
||
Line 9,697: | Line 9,697: | ||
[5,_,_,_,_,_,_,7,3], |
[5,_,_,_,_,_,_,7,3], |
||
[_,_,2,_,1,_,_,_,_], |
[_,_,2,_,1,_,_,_,_], |
||
[_,_,_,_,4,_,_,_,9]]).</ |
[_,_,_,_,4,_,_,_,9]]).</syntaxhighlight> |
||
===GNU Prolog version=== |
===GNU Prolog version=== |
||
{{works with|GNU Prolog|1.4.4}} |
{{works with|GNU Prolog|1.4.4}} |
||
< |
<syntaxhighlight lang="prolog">:- initialization(main). |
||
Line 9,754: | Line 9,754: | ||
main :- test(T), solve(T), maplist(show,T), halt. |
main :- test(T), solve(T), maplist(show,T), halt. |
||
show(X) :- write(X), nl.</ |
show(X) :- write(X), nl.</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>[1,2,3,4,5,6,7,8,9] |
<pre>[1,2,3,4,5,6,7,8,9] |
||
Line 9,769: | Line 9,769: | ||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
A brute force method is used, it seemed the fastest as well as the simplest. |
A brute force method is used, it seemed the fastest as well as the simplest. |
||
< |
<syntaxhighlight lang="purebasic">DataSection |
||
puzzle: |
puzzle: |
||
Data.s "394002670" |
Data.s "394002670" |
||
Line 9,879: | Line 9,879: | ||
Input() |
Input() |
||
CloseConsole() |
CloseConsole() |
||
EndIf</ |
EndIf</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>+-----+-----+-----+ |
<pre>+-----+-----+-----+ |
||
Line 9,913: | Line 9,913: | ||
A simple backtrack algorithm -- Quick but may take longer if the grid had been more than 9 x 9 |
A simple backtrack algorithm -- Quick but may take longer if the grid had been more than 9 x 9 |
||
< |
<syntaxhighlight lang="python"> |
||
def initiate(): |
def initiate(): |
||
box.append([0, 1, 2, 9, 10, 11, 18, 19, 20]) |
box.append([0, 1, 2, 9, 10, 11, 18, 19, 20]) |
||
Line 9,997: | Line 9,997: | ||
print grid[i*9:i*9+9] |
print grid[i*9:i*9+9] |
||
raw_input() |
raw_input() |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
Line 10,006: | Line 10,006: | ||
===Brute Force=== |
===Brute Force=== |
||
{{trans|Perl}} |
{{trans|Perl}} |
||
<lang |
<syntaxhighlight lang="raku" line>my @A = < |
||
5 3 0 0 2 4 7 0 0 |
5 3 0 0 2 4 7 0 0 |
||
0 0 2 0 0 0 8 0 0 |
0 0 2 0 0 0 8 0 0 |
||
Line 10,046: | Line 10,046: | ||
} |
} |
||
} |
} |
||
solve;</ |
solve;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 10,064: | Line 10,064: | ||
This is an alternative solution that uses a more ellaborate set of choices instead of brute-forcing it. |
This is an alternative solution that uses a more ellaborate set of choices instead of brute-forcing it. |
||
<lang |
<syntaxhighlight lang="raku" line># |
||
# In this code, a sudoku puzzle is represented as a two-dimentional |
# In this code, a sudoku puzzle is represented as a two-dimentional |
||
# array. The cells that are not yet solved are represented by yet |
# array. The cells that are not yet solved are represented by yet |
||
Line 10,285: | Line 10,285: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 10,303: | Line 10,303: | ||
A sudoku is represented as a matrix, see Rascal solutions to matrix related problems for examples. |
A sudoku is represented as a matrix, see Rascal solutions to matrix related problems for examples. |
||
< |
<syntaxhighlight lang="rascal">import Prelude; |
||
import vis::Figure; |
import vis::Figure; |
||
import vis::Render; |
import vis::Render; |
||
Line 10,386: | Line 10,386: | ||
<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,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> |
<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> |
||
};</ |
};</syntaxhighlight> |
||
Example |
Example |
||
Line 10,679: | Line 10,679: | ||
Example of a back-tracking solver, from [[wp:Algorithmics of sudoku]] |
Example of a back-tracking solver, from [[wp:Algorithmics of sudoku]] |
||
{{works with|Ruby|2.0+}} |
{{works with|Ruby|2.0+}} |
||
< |
<syntaxhighlight lang="ruby">def read_matrix(data) |
||
lines = data.lines |
lines = data.lines |
||
9.times.collect { |i| 9.times.collect { |j| lines[i][j].to_i } } |
9.times.collect { |i| 9.times.collect { |j| lines[i][j].to_i } } |
||
Line 10,769: | Line 10,769: | ||
print_matrix(matrix) |
print_matrix(matrix) |
||
puts |
puts |
||
print_matrix(solve_sudoku(matrix))</ |
print_matrix(solve_sudoku(matrix))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 10,803: | Line 10,803: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
{{trans|Ada}} |
{{trans|Ada}} |
||
< |
<syntaxhighlight lang="rust">type Sudoku = [u8; 81]; |
||
fn is_valid(val: u8, x: usize, y: usize, sudoku_ar: &mut Sudoku) -> bool { |
fn is_valid(val: u8, x: usize, y: usize, sudoku_ar: &mut Sudoku) -> bool { |
||
Line 10,866: | Line 10,866: | ||
println!("Unsolvable"); |
println!("Unsolvable"); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 10,888: | Line 10,888: | ||
Use CLP solver in SAS/OR: |
Use CLP solver in SAS/OR: |
||
< |
<syntaxhighlight lang="sas">/* define SAS data set */ |
||
data Indata; |
data Indata; |
||
input C1-C9; |
input C1-C9; |
||
Line 10,934: | Line 10,934: | ||
/* print solution */ |
/* print solution */ |
||
print X; |
print X; |
||
quit;</ |
quit;</syntaxhighlight> |
||
Output: |
Output: |
||
Line 10,955: | Line 10,955: | ||
This solver works with normally 9x9 sudokus as well as with sudokus of jigsaw type or sudokus with additional condition like diagonal constraint. |
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}} |
{{works with|Scala|2.9.1}} |
||
< |
<syntaxhighlight lang="scala">object SudokuSolver extends App { |
||
class Solver { |
class Solver { |
||
Line 11,086: | Line 11,086: | ||
println(solution match {case Nil => "no solution!!!" case _ => f2Str(solution)}) |
println(solution match {case Nil => "no solution!!!" case _ => f2Str(solution)}) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>riddle: |
<pre>riddle: |
||
Line 11,120: | Line 11,120: | ||
The implementation above doesn't work so effective for sudokus like Bracmat version, therefore I implemented a second version inspired by Java section: |
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}} |
{{works with|Scala|2.9.1}} |
||
< |
<syntaxhighlight lang="scala">object SudokuSolver extends App { |
||
object Solver { |
object Solver { |
||
Line 11,237: | Line 11,237: | ||
+("\n"*2)) |
+("\n"*2)) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>riddle used in Ada section: |
<pre>riddle used in Ada section: |
||
Line 11,368: | Line 11,368: | ||
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. |
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. |
||
<lang>Init_board=[... |
<syntaxhighlight lang="text">Init_board=[... |
||
5 3 0 0 7 0 0 0 0;... |
5 3 0 0 7 0 0 0 0;... |
||
6 0 0 1 9 5 0 0 0;... |
6 0 0 1 9 5 0 0 0;... |
||
Line 11,540: | Line 11,540: | ||
disp('Invalid solution found.'); |
disp('Invalid solution found.'); |
||
disp_board(Solved_board); |
disp_board(Solved_board); |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 11,600: | Line 11,600: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="ruby">func check(i, j) is cached { |
||
var (id, im) = i.divmod(9) |
var (id, im) = i.divmod(9) |
||
var (jd, jm) = j.divmod(9) |
var (jd, jm) = j.divmod(9) |
||
Line 11,648: | Line 11,648: | ||
) |
) |
||
solve(grid)</ |
solve(grid)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>5 3 9 8 2 4 7 6 1 |
<pre>5 3 9 8 2 4 7 6 1 |
||
Line 11,663: | Line 11,663: | ||
=={{header|Shale}}== |
=={{header|Shale}}== |
||
< |
<syntaxhighlight lang="shale"> |
||
#!/usr/local/bin/shale |
#!/usr/local/bin/shale |
||
Line 12,193: | Line 12,193: | ||
// I'd like to see an irregular sudoku with a knight's move constraint. Any takers... |
// I'd like to see an irregular sudoku with a knight's move constraint. Any takers... |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''Output''' |
'''Output''' |
||
Line 12,234: | Line 12,234: | ||
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'''. |
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'''. |
||
< |
<syntaxhighlight lang="sql">with |
||
symbols (d) as (select to_char(level) from dual connect by level <= 9) |
symbols (d) as (select to_char(level) from dual connect by level <= 9) |
||
, board (i) as (select level from dual connect by level <= 81) |
, board (i) as (select level from dual connect by level <= 81) |
||
Line 12,262: | Line 12,262: | ||
from r |
from r |
||
where pos = 0 |
where pos = 0 |
||
;</ |
;</syntaxhighlight> |
||
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. |
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,286: | Line 12,286: | ||
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. |
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. |
||
< |
<syntaxhighlight lang="stata">mata |
||
function sudoku(a) { |
function sudoku(a) { |
||
s = J(81,20,.) |
s = J(81,20,.) |
||
Line 12,386: | Line 12,386: | ||
sudoku(a) |
sudoku(a) |
||
a |
a |
||
end</ |
end</syntaxhighlight> |
||
'''Output''' |
'''Output''' |
||
Line 12,407: | Line 12,407: | ||
Two more examples, from [http://www.7sudoku.com/very-difficult here] and [http://www.extremesudoku.info/sudoku.html there]. |
Two more examples, from [http://www.7sudoku.com/very-difficult here] and [http://www.extremesudoku.info/sudoku.html there]. |
||
< |
<syntaxhighlight lang="stata">a = 7,9,.,.,.,3,.,.,2\ |
||
.,6,.,5,1,.,.,.,.\ |
.,6,.,5,1,.,.,.,.\ |
||
.,.,.,.,.,2,.,.,6\ |
.,.,.,.,.,2,.,.,6\ |
||
Line 12,459: | Line 12,459: | ||
8 | 3 8 5 4 7 9 2 1 6 | |
8 | 3 8 5 4 7 9 2 1 6 | |
||
9 | 7 6 9 3 2 1 4 5 8 | |
9 | 7 6 9 3 2 1 4 5 8 | |
||
+-------------------------------------+</ |
+-------------------------------------+</syntaxhighlight> |
||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="swift">import Foundation |
||
typealias SodukuPuzzle = [[Int]] |
typealias SodukuPuzzle = [[Int]] |
||
Line 12,586: | Line 12,586: | ||
let puzzle = Soduku(board: board) |
let puzzle = Soduku(board: board) |
||
puzzle.solve() |
puzzle.solve() |
||
puzzle.printBoard()</ |
puzzle.printBoard()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 12,606: | Line 12,606: | ||
{{works with|Swift 3}} |
{{works with|Swift 3}} |
||
<syntaxhighlight lang="swift"> |
|||
<lang Swift> |
|||
func solving(board: [[Int]]) -> [[Int]] { |
func solving(board: [[Int]]) -> [[Int]] { |
||
var board = board |
var board = board |
||
Line 12,671: | Line 12,671: | ||
print(solving(board: puzzle)) |
print(solving(board: puzzle)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 12,690: | Line 12,690: | ||
< |
<syntaxhighlight lang="systemverilog"> |
||
////////////////////////////////////////////////////////////////////////////// |
////////////////////////////////////////////////////////////////////////////// |
||
Line 12,820: | Line 12,820: | ||
end |
end |
||
endprogram |
endprogram |
||
</syntaxhighlight> |
|||
</lang> |
|||
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. |
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,875: | Line 12,875: | ||
=={{header|Tailspin}}== |
=={{header|Tailspin}}== |
||
< |
<syntaxhighlight lang="tailspin"> |
||
templates deduceRemainingDigits |
templates deduceRemainingDigits |
||
templates findOpenPosition |
templates findOpenPosition |
||
Line 13,021: | Line 13,021: | ||
'> 'solves sudoku and outputs pretty solution' |
'> 'solves sudoku and outputs pretty solution' |
||
end 'sudoku solver' |
end 'sudoku solver' |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
Line 13,028: | Line 13,028: | ||
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. |
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}} |
{{works with|Tcl|8.6}} or {{libheader|TclOO}} |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.6 |
||
oo::class create Sudoku { |
oo::class create Sudoku { |
||
variable idata |
variable idata |
||
Line 13,276: | Line 13,276: | ||
return 0 |
return 0 |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Demonstration code: |
Demonstration code: |
||
< |
<syntaxhighlight lang="tcl">SudokuSolver create sudoku |
||
sudoku load { |
sudoku load { |
||
{3 9 4 @ @ 2 6 7 @} |
{3 9 4 @ @ 2 6 7 @} |
||
Line 13,301: | Line 13,301: | ||
} |
} |
||
} |
} |
||
sudoku destroy</ |
sudoku destroy</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>+-----+-----+-----+ |
<pre>+-----+-----+-----+ |
||
Line 13,317: | Line 13,317: | ||
+-----+-----+-----+</pre> |
+-----+-----+-----+</pre> |
||
If we'd added a logger method (after creating the <code>sudoku</code> object but before running the solver) like this: |
If we'd added a logger method (after creating the <code>sudoku</code> object but before running the solver) like this: |
||
< |
<syntaxhighlight lang="tcl">oo::objdefine sudoku method Log msg {puts $msg}</syntaxhighlight> |
||
Then this additional logging output would have been produced prior to the result being printed: |
Then this additional logging output would have been produced prior to the result being printed: |
||
<pre>::RuleOnlyChoice solved ::sudoku at 8,0 for 1 |
<pre>::RuleOnlyChoice solved ::sudoku at 8,0 for 1 |
||
Line 13,371: | Line 13,371: | ||
=={{header|Ursala}}== |
=={{header|Ursala}}== |
||
< |
<syntaxhighlight lang="ursala">#import std |
||
#import nat |
#import nat |
||
Line 13,383: | Line 13,383: | ||
~&rgg&& ~&irtPFXlrjrXPS; ~&lrK2tkZ2g&& ~&llrSL2rDrlPrrPljXSPTSL)+-, |
~&rgg&& ~&irtPFXlrjrXPS; ~&lrK2tkZ2g&& ~&llrSL2rDrlPrrPljXSPTSL)+-, |
||
//~&p ^|DlrDSLlrlPXrrPDSL(~&,num*+ rep2 block3)*= num block27 ~&iiK0 iota9, |
//~&p ^|DlrDSLlrlPXrrPDSL(~&,num*+ rep2 block3)*= num block27 ~&iiK0 iota9, |
||
* `0?=\~&iNC ! ~&t digits+-</ |
* `0?=\~&iNC ! ~&t digits+-</syntaxhighlight> |
||
test program: |
test program: |
||
< |
<syntaxhighlight lang="ursala">#show+ |
||
example = |
example = |
||
Line 13,400: | Line 13,400: | ||
010067008 |
010067008 |
||
009008000 |
009008000 |
||
026400735]-</ |
026400735]-</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 13,418: | Line 13,418: | ||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
{{trans|Fortran}} |
{{trans|Fortran}} |
||
< |
<syntaxhighlight lang="vb">Dim grid(9, 9) |
||
Dim gridSolved(9, 9) |
Dim gridSolved(9, 9) |
||
Line 13,519: | Line 13,519: | ||
Debug.Print |
Debug.Print |
||
Next i |
Next i |
||
End Sub</ |
End Sub</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 13,538: | Line 13,538: | ||
{{trans|VBA}} |
{{trans|VBA}} |
||
To run in console mode with cscript. |
To run in console mode with cscript. |
||
< |
<syntaxhighlight lang="vb">Dim grid(9, 9) |
||
Dim gridSolved(9, 9) |
Dim gridSolved(9, 9) |
||
Line 13,639: | Line 13,639: | ||
End Sub 'Sudoku |
End Sub 'Sudoku |
||
Call sudoku</ |
Call sudoku</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Problem: |
<pre>Problem: |
||
Line 13,664: | Line 13,664: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="ecmascript">class Sudoku { |
||
construct new(rows) { |
construct new(rows) { |
||
if (rows.count != 9 || rows.any { |r| r.count != 9 }) { |
if (rows.count != 9 || rows.any { |r| r.count != 9 }) { |
||
Line 13,741: | Line 13,741: | ||
"000036040" |
"000036040" |
||
] |
] |
||
Sudoku.new(rows).solve()</ |
Sudoku.new(rows).solve()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 13,778: | Line 13,778: | ||
can be verified by several other examples. |
can be verified by several other examples. |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="xpl0">code ChOut=8, CrLf=9, IntOut=11, Text=12; |
||
proc Show(X); |
proc Show(X); |
||
Line 13,848: | Line 13,848: | ||
..9 ..8 ... |
..9 ..8 ... |
||
.26 4.. 735 "); |
.26 4.. 735 "); |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 13,867: | Line 13,867: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|C}} Note: Unlike in the C solution, 1<<-1 is defined (as 0). |
{{trans|C}} Note: Unlike in the C solution, 1<<-1 is defined (as 0). |
||
< |
<syntaxhighlight lang="zkl">fcn trycell(sdku,pos=0){ |
||
row,col:=pos/9, pos%9; |
row,col:=pos/9, pos%9; |
||
Line 13,888: | Line 13,888: | ||
sdku[pos]=0; |
sdku[pos]=0; |
||
return(False); |
return(False); |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">problem:= |
||
#<<< |
#<<< |
||
" 5 3 0 0 7 0 0 0 0 |
" 5 3 0 0 7 0 0 0 0 |
||
Line 13,907: | Line 13,907: | ||
s[n*27,27].pump(Console.println,T(Void.Read,8),("| " + "%s%s%s | "*3).fmt); // 3 lines |
s[n*27,27].pump(Console.println,T(Void.Read,8),("| " + "%s%s%s | "*3).fmt); // 3 lines |
||
println("+-----+-----+-----+"); |
println("+-----+-----+-----+"); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |