Sudoku: Difference between revisions
Content deleted Content added
m →Recursive Backtrack Solution: Changed C# Version this works with |
Added Uiua solution |
||
(85 intermediate revisions by 14 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#}}==
===
{{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;
using System;
using System.Runtime.CompilerServices;
namespace
internal readonly record struct Square (int Row, int Col);
internal record Constraints (IEnumerable<int> ConstrainedRange, Square Square);
internal class Cache : Dictionary<Square, Constraints> { };
internal record CacheGrid (int[][] Grid, Cache Cache);
internal static class SudokuFastMemoBFS {
internal static U Fwd<T, U>(this T data, Func<T, U> f) => f(data);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static int RowCol(int rc) => rc <= 2 ? 0 : rc <= 5 ? 3 : 6;
private static bool
if (cg.Cache.Count == finished || cg.Solve(cg.Next(constraints.Square), finished))
return true;
}
return false;
}
private static
private static readonly int[]
private static bool Valid(this int[][] grid, int row, int col, int val) {
for (var i =
if (grid[row][i] == val || grid[i][col] == val)
return false;
for (var r = RowCol(row); r < RowCol(row) + 3; r++)
for (var c = RowCol(col); c < RowCol(col) + 3; c++)
if (grid[r][c] == val)
return false;
return true;
}
private static IEnumerable<int> Constraints(this int[][] grid, int row, int col) =>
range.Where(val => grid.Valid(row, col, val));
private static Constraints Next(this CacheGrid cg, Square square) =>
cg.Cache.ContainsKey(square)
? cg.Cache[square]
: cg.Cache[square]=cg.Grid.SortedCells();
private static Constraints SortedCells(this int[][] grid) =>
(from row in domain
from col in domain
where grid[row][col] == 0
let cell = new Constraints(grid.Constraints(row, col), new Square(row, col))
orderby cell.ConstrainedRange.Count() ascending
select cell).First();
private static CacheGrid Parse(string input) =>
input
.Select((c, i) => (index: i, val: int.Parse(c.ToString())))
.GroupBy(id => id.index / 9)
.Select(grp => grp.Select(id => id.val).ToArray())
.ToArray()
.Fwd(grid => new CacheGrid(grid, new Cache()));
public static string
public static int[][] Run(string input)
var marked = cg.Grid.SelectMany(row
return cg.Solve(cg.Grid.SortedCells(), 80 - marked) ? cg.Grid : new int[][] { Array.Empty<int>() };
}
}
}</syntaxhighlight>
Usage
<syntaxhighlight lang="csharp">using System.Linq;
using static System.Linq.Enumerable;
using static System.Console;
using System.IO;
namespace SodukoFastMemoBFS {
static void Main(string[] args) {
var
var puzzles =
var single = puzzles.First();
var
watch.Stop();
WriteLine($"Doing {num}
watch.Reset();
watch.Start();
SudokuFastMemoBFS.Run(puzzle);
watch.Stop();
total += watch.ElapsedMilliseconds;
Write(".");
}
watch.Stop();
WriteLine($"\nPuzzles:{num}, Total:{total} ms, Average:{total / num:0.00} ms");
ReadKey();
}
}
}</syntaxhighlight>
Output
<pre>693784512
487512936
125963874
932651487
568247391
741398625
319475268
856129743
274836159
000000010400000000020000000000050407008000300001090000300400200050100000000806000: 336 ms
Doing 100 puzzles
....................................................................................................
Puzzles:100, Total:5316 ms, Average:53.16 ms</pre>
===Solver===
{{libheader|Microsoft Solver Foundation}}
<!-- By Nigel Galloway, Jan 29, 2012 -->
<
namespace Sudoku
Line 1,996 ⟶ 2,032:
}
}
}</
Produces:
<pre>
Line 2,012 ⟶ 2,048:
</pre>
===
<
using System.Collections.Generic;
using System.Text;
Line 2,291 ⟶ 2,327:
public static string DelimitWith<T>(this IEnumerable<T> source, string separator) => string.Join(separator, source);
}</
{{out}}
<pre>
Line 2,316 ⟶ 2,352:
=={{header|C++}}==
{{trans|Java}}
<
using namespace std;
Line 2,407 ⟶ 2,443:
ss.solve();
return EXIT_SUCCESS;
}</
=={{header|Clojure}}==
<
(:use [clojure.pprint :only (cl-format)]))
Line 2,433 ⟶ 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,455 ⟶ 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,498 ⟶ 2,534:
(setf (aref grid row column) choice)
(when (eq grid (solve grid row (1+ column)))
(return grid))))))</
Example:
<pre>> (defparameter *puzzle*
Line 2,525 ⟶ 2,561:
(7 5 9 2 3 8 1 4 6)
(8 2 6 4 1 9 7 3 5))</pre>
=={{header|Crystal}}==
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)
board[row].includes?(number)
end
def isNumberInColumn(board, number, column)
board.any?{|row| row[column] == number }
end
def isNumberInBox(board, number, row, column)
localBoxRow = row - row % 3
localBoxColumn = column - column % 3
(localBoxRow...(localBoxRow+3)).each do |i|
(localBoxColumn...(localBoxColumn+3)).each do |j|
return true if board[i][j] == number
end
end
false
end
def isValidPlacement(board, number, row, column)
return !isNumberInRow(board, number, row) &&
!isNumberInColumn(board, number, column) &&
!isNumberInBox(board, number, row, column)
end
def solveBoard(board)
board.each_with_index do |row, i|
row.each_with_index do |cell, j|
if(cell == 0)
(1..GRID_SIZE).each do |n|
if(isValidPlacement(board,n,i,j))
board[i][j]=n
if(solveBoard(board))
return true
else
board[i][j]=0
end
end
end
return false
end
end
end
return true
end
def printBoard(board)
board.each_with_index do |row, i|
row.each_with_index do |cell, j|
print cell
print '|' if j == 2 || j == 5
print '\n' if j == 8
end
print "-"*11 + '\n' if i == 2 || i == 5
end
print '\n'
end
board = [
[7, 0, 2, 0, 5, 0, 6, 0, 0],
[0, 0, 0, 0, 0, 3, 0, 0, 0],
[1, 0, 0, 0, 0, 9, 5, 0, 0],
[8, 0, 0, 0, 0, 0, 0, 9, 0],
[0, 4, 3, 0, 0, 0, 7, 5, 0],
[0, 9, 0, 0, 0, 0, 0, 0, 8],
[0, 0, 9, 7, 0, 0, 0, 0, 5],
[0, 0, 0, 2, 0, 0, 0, 0, 0],
[0, 0, 7, 0, 4, 0, 2, 0, 3]]
printBoard(board)
if(solveBoard(board))
printBoard(board)
end
</syntaxhighlight>
{{out}}
<pre>
702|050|600
000|003|000
100|009|500
-----------
800|000|090
043|000|750
090|000|008
-----------
009|700|005
000|200|000
007|040|203
732|458|619
956|173|824
184|629|537
-----------
871|564|392
643|892|751
295|317|468
-----------
329|786|145
418|235|976
567|941|283
</pre>
=={{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,590 ⟶ 2,728:
" 5 7 921 ",
" 64 9 ",
" 2 438"]</
Line 2,596 ⟶ 2,734:
{{Works with|PAKCS}}
Minimal w/o read or show utilities.
<
import Constraint (allC)
import List (transpose)
Line 2,629 ⟶ 2,767:
, [7,_,_,6,_,_,5,_,_]
]
main | sudoku xs = xs where xs = test</
{{Out}}
<pre>Execution time: 0 msec. / elapsed: 10 msec.
Line 2,637 ⟶ 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,763 ⟶ 2,901:
else
solution.get.representSudoku.writeln;
}</
{{out}}
<pre>8 5 . | . . 2 | 4 . .
Line 2,791 ⟶ 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,824 ⟶ 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,838 ⟶ 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 2,879 ⟶ 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,008 ⟶ 3,146:
ShowMessage('Solved!');
end;
end;</
Usage:
<
SudokuSolver: TSudokuSolver;
begin
Line 3,027 ⟶ 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,267 ⟶ 3,421:
{{3, 8}, 2}, {{5, 8}, 1},
{{5, 9}, 4}, {{9, 9}, 9}]
Sudoku.task( difficult )</
{{out}}
Line 3,327 ⟶ 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,490 ⟶ 3,644:
display( Solved ),
io:nl().
</syntaxhighlight>
{{out}}
<pre>
Line 3,574 ⟶ 3,728:
0 is the empty cell.
<syntaxhighlight lang="erre">
!--------------------------------------------------------------------
! risolve Sudoku: in input il file SUDOKU.TXT
Line 3,981 ⟶ 4,135:
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
===
<!-- By Martin Freedman, 26/11/2021 -->
<syntaxhighlight lang="fsharp">module SudokuBacktrack
//Helpers
let tuple2 a b = a,b
let flip f a b = f b a
let (>>=) f g = Option.bind g f
/// "A1" to "I9" squares as key in values dictionary
let key a b = $"{a}{b}"
/// Cross product of elements in ax and elements in bx
let cross ax bx = [| for a in ax do for b in bx do key a b |]
// constants
let valid = "1234567890.,"
let rows = "ABCDEFGHI"
let cols = "123456789"
let squares = cross rows cols
// List of all row, cols and boxes: aka units
let unitList =
[for c in cols do cross rows (string c) ]@ // row units
[for r in rows do cross (string r) cols ]@ // col units
[for rs in ["ABC";"DEF";"GHI"] do for cs in ["123";"456";"789"] do cross rs cs ] // box units
/// Dictionary of units for each square
let units =
[for s in squares do s, [| for u in unitList do if u |> Array.contains s then u |] ] |> Map.ofSeq
/// Dictionary of all peer squares in the relevant units wrt square in question
let peers =
[for s in squares do units[s] |> Array.concat |> Array.distinct |> Array.except [s] |> tuple2 s] |> Map.ofSeq
/// Should parse grid in many input formats or return None
let parseGrid grid =
let ints = [for c in grid do if valid |> Seq.contains c then if ",." |> Seq.contains c then 0 else (c |> string |> int)]
if Seq.length ints = 81 then ints |> Seq.zip squares |> Map.ofSeq |> Some else None
/// Outputs single line puzzle with 0 as empty squares
let asString = function
| Some values -> values |> Map.toSeq |> Seq.map (snd>>string) |> String.concat ""
| _ -> "No solution or Parse Failure"
/// Outputs puzzle in 2D format with 0 as empty squares
let prettyPrint = function
| Some (values:Map<_,_>) ->
[for r in rows do [for c in cols do (values[key r c] |> string) ] |> String.concat " " ] |> String.concat "\n"
| _ -> "No solution or Parse Failure"
/// Is digit allowed in the square in question? !!! hot path !!!!
/// Array/Array2D no faster and they need explicit copy since not immutable
let constraints (values:Map<_,_>) s d = peers[s] |> Seq.map (fun p -> values[p]) |> Seq.exists ((=) d) |> not
/// Move to next square or None if out of bounds
let next s = squares |> Array.tryFindIndex ((=)s) |> function Some i when i + 1 < 81 -> Some squares[i + 1] | _ -> None
/// Backtrack recursively and immutably from index
let rec backtracker (values:Map<_,_>) = function
| None -> Some values // solved!
| Some s when values[s] > 0 -> backtracker values (next s) // square not empty
| Some s ->
let rec tracker = function
| [] -> None
| d::dx ->
values
|> Map.change s (Option.map (fun _ -> d))
|> flip backtracker (next s)
|> function
| None -> tracker dx
| success -> success
[for d in 1..9 do if constraints values s d then d] |> tracker
/// solve sudoku using simple backtracking
let solve grid = grid |> parseGrid >>= flip backtracker (Some "A1")</syntaxhighlight>
'''Usage:'''
<syntaxhighlight lang="fsharp">open System
open SudokuBacktrack
[<EntryPoint>]
let main argv =
let puzzle = "000028000800010000000000700000600403200004000100700000030400500000000010060000000"
puzzle |> printfn "Puzzle:\n%s"
puzzle |> parseGrid |> prettyPrint |> printfn "Formatted:\n%s"
puzzle |> solve |> prettyPrint |> printfn "Solution:\n%s"
printfn "Press any key to exit"
Console.ReadKey() |> ignore
0</syntaxhighlight>
{{Output}}<pre>
Puzzle:
000028000800010000000000700000600403200004000100700000030400500000000010060000000
Formatted:
0 0 0 0 2 8 0 0 0
8 0 0 0 1 0 0 0 0
0 0 0 0 0 0 7 0 0
0 0 0 6 0 0 4 0 3
2 0 0 0 0 4 0 0 0
1 0 0 7 0 0 0 0 0
0 3 0 4 0 0 5 0 0
0 0 0 0 0 0 0 1 0
0 6 0 0 0 0 0 0 0
Solution:
6 1 7 3 2 8 9 4 5
8 9 4 5 1 7 2 3 6
3 2 5 9 4 6 7 8 1
9 7 8 6 5 1 4 2 3
2 5 6 8 3 4 1 7 9
1 4 3 7 9 2 6 5 8
7 3 1 4 8 9 5 6 2
4 8 9 2 6 5 3 1 7
5 6 2 1 7 3 8 9 4
Press any key to exit
</pre>
===Constraint Satisfaction (Norvig)===
<!-- 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
module SudokuCPSArray
open System
/// from 11 to 99 as squares key maps to 0 to 80 in arrays
let key a b = (9*a + b) - 10
/// Keys generator
let cross ax bx = [| for a in ax do for b in bx do key a b |]
let digits = [|1..9|]
let rows = digits
let cols = digits
let empty = "0,."
let valid = "123456789"+empty
let boxi = [for b in 1..3..9 -> [|b..b+2|]]
let squares = cross rows cols
/// List of all row, cols and boxes: aka units
let unitlist =
[for c in cols -> cross rows [|c|] ]@
[for r in rows -> cross [|r|] cols ]@
[for rs in boxi do for cs in boxi do cross rs cs ]
/// Dictionary of units for each square
let units =
[|for s in squares do [| for u in unitlist do if u |> Array.contains s then u |] |]
/// Dictionary of all peer squares in the relevant units wrt square in question
let peers =
[| for s in squares do units[s] |> Array.concat |> Array.distinct |> Array.except [s] |]
/// folds folder returning Some on completion or returns None if not
let rec all folder state source =
match state, source with
| None, _ -> None
| Some st, [] -> Some st
| Some st , hd::rest -> folder st hd |> (fun st1 -> all folder st1 rest)
/// Assign digit d to values[s] and propagate (via eliminate)
/// Return Some values, except None if a contradiction is detected.
let rec assign (values:int[][]) (s) d =
values[s]
|> Array.filter ((<>)d)
|> List.ofArray |> all (fun vx d1 -> eliminate vx s d1) (Some values)
/// Eliminate digit d from values[s] and propagate when values[s] size is 1.
/// Return Some values, except return None if a contradiction is detected.
and eliminate (values:int[][]) s d =
let peerElim (values1:int[][]) = // If a square s is reduced to one value d, then *eliminate* d from the peers.
match Seq.length values1[s] with
| 0 -> None // contradiction - removed last value
| 1 -> peers[s] |> List.ofArray |> all (fun vx1 s1 -> eliminate vx1 s1 (values1[s] |> Seq.head) ) (Some values1)
| _ -> Some values1
let unitsElim values1 = // If a unit u is reduced to only one place for a value d, then *assign* it there.
units[s]
|> List.ofArray
|> all (fun (vx1:int[][]) u ->
let sx = [for s in u do if vx1[s] |> Seq.contains d then s]
match Seq.length sx with
| 0 -> None
| 1 -> assign vx1 (Seq.head sx) d
| _ -> Some vx1) (Some values1)
match values[s] |> Seq.contains d with
| false -> Some values // Already eliminated, nothing to do
| true ->
values[s] <- values[s]|> Array.filter ((<>)d)
values
|> peerElim
|> Option.bind unitsElim
/// Convert grid into a Map of {square: char} with "0","."or"," for empties.
let parseGrid grid =
let cells = [for c in grid do if valid |> Seq.contains c then if empty |> Seq.contains c then 0 else ((string>>int)c)]
if Seq.length cells = 81 then cells |> Seq.zip squares |> Map.ofSeq |> Some else None
/// Convert grid to a Map of constraint propagated possible values, or return None if a contradiction is detected.
let applyCPS (parsedGrid:Map<_,_>) =
let values = [| for s in squares do digits |]
parsedGrid
|> Seq.filter (fun (KeyValue(_,d)) -> digits |> Seq.contains d)
|> List.ofSeq
|> all (fun vx (KeyValue(s,d)) -> assign vx s d) (Some values)
/// Calculate string centre for each square - which can contain more than 1 digit when debugging
let centre s width =
let n = width - (Seq.length s)
if n <= 0 then s
else
let half = n/2 + (if (n%2>0 && width%2>0) then 1 else 0)
sprintf "%s%s%s" (String(' ',half)) s (String(' ', n - half))
/// Display these values as a 2-D grid. Used for debugging
let prettyPrint (values:int[][]) =
let asString = Seq.map string >> String.concat ""
let width = 1 + ([for s in squares do Seq.length values[s]] |> List.max)
let line = sprintf "%s\n" ((String('-',width*3) |> Seq.replicate 3) |> String.concat "+")
[for r in rows do
for c in cols do
sprintf "%s%s" (centre (asString values[key r c]) width) (if List.contains c [3;6] then "|" else "")
sprintf "\n%s"(if List.contains r [3;6] then line else "") ]
|> String.concat ""
/// Outputs single line puzzle with 0 as empty squares
let asString values = values |> Map.toSeq |> Seq.map (snd>>string) |> String.concat ""
let copy values = values |> Array.map Array.copy
/// Using depth-first search and propagation, try all possible values.
let rec search (values:int[][])=
[for s in squares do if Seq.length values[s] > 1 then Seq.length values[s] ,s]
|> function
| [] -> Some values // Solved!
| list -> // tryPick ~ Norvig's `some`
list |> List.minBy fst
|> fun (_,s) -> values[s] |> Seq.tryPick (fun d -> assign (copy values) s d |> (Option.bind search))
let run n g f = parseGrid >> function None -> n | Some m -> f m |> g
let solver = run "Parse Error" (Option.fold (fun _ t -> t |> prettyPrint) "No Solution")
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)) </syntaxhighlight>
'''Usage'''<syntaxhighlight lang="fsharp">open System
open SudokuCPSArray
open System.Diagnostics
open System.IO
[<EntryPoint>]
let main argv =
printfn "Easy board solution automatic with constraint propagation"
let easy = "..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3.."
easy |> solveNoSearch |> printfn "%s"
printfn "Simple elimination not possible"
let simple = "4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......"
simple |> run "Parse Error" asString id |> printfn "%s"
simple |> solveNoSearch |> printfn "%s"
printfn "Try again with search:"
simple |> solveWithSearch |> printfn "%s"
let watch = Stopwatch()
let hard = "85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4."
printfn "Hard"
watch.Start()
hard |> solveWithSearch |> printfn "%s"
watch.Stop()
printfn $"Elapsed milliseconds = {watch.ElapsedMilliseconds } ms"
watch.Reset()
let puzzles =
if Seq.length argv = 1 then
let num = argv[0] |> int
printfn $"First {num} puzzles in sudoku17 (http://staffhome.ecm.uwa.edu.au/~00013890/sudoku17)"
File.ReadLines(@"sudoku17.txt") |> Seq.take num |>Array.ofSeq
else
printfn $"All puzzles in sudoku17 (http://staffhome.ecm.uwa.edu.au/~00013890/sudoku17)"
File.ReadLines(@"sudoku17.txt") |>Array.ofSeq
watch.Start()
let result = puzzles |> Array.map solveWithSearchToMapOnly
watch.Stop()
if result |> Seq.forall Option.isSome then
let total = watch.ElapsedMilliseconds
let avg = (float total) /(float result.Length)
printfn $"\nPuzzles:{result.Length}, Total:%.2f{((float)total)/1000.0} s, Average:%.2f{avg} ms"
else
printfn "Some sudoku17 puzzles failed"
Console.ReadKey() |> ignore
0</syntaxhighlight>
{{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
9 6 7 |3 4 5 |8 2 1
2 5 1 |8 7 6 |4 9 3
------+------+------
5 4 8 |1 3 2 |9 7 6
7 2 9 |5 6 4 |1 3 8
1 3 6 |7 9 8 |2 4 5
------+------+------
3 7 2 |6 8 9 |5 1 4
8 1 4 |2 5 3 |7 6 9
6 9 5 |4 1 7 |3 8 2
Simple elimination not possible
400000805030000000000700000020000060000080400000010000000603070500200000104000000
4 1679 12679 | 139 2369 269 | 8 1239 5
26789 3 1256789 | 14589 24569 245689 | 12679 1249 124679
2689 15689 125689 | 7 234569 245689 | 12369 12349 123469
------------------------+------------------------+------------------------
3789 2 15789 | 3459 34579 4579 | 13579 6 13789
3679 15679 15679 | 359 8 25679 | 4 12359 12379
36789 4 56789 | 359 1 25679 | 23579 23589 23789
------------------------+------------------------+------------------------
289 89 289 | 6 459 3 | 1259 7 12489
5 6789 3 | 2 479 1 | 69 489 4689
1 6789 4 | 589 579 5789 | 23569 23589 23689
Try again with search:
4 1 7 |3 6 9 |8 2 5
6 3 2 |1 5 8 |9 4 7
9 5 8 |7 2 4 |3 1 6
------+------+------
8 2 5 |4 3 7 |1 6 9
7 9 1 |5 8 6 |4 3 2
3 4 6 |9 1 2 |7 5 8
------+------+------
2 8 9 |6 4 3 |5 7 1
5 7 3 |2 9 1 |6 8 4
1 6 4 |8 7 5 |2 9 3
Hard
8 5 9 |6 1 2 |4 3 7
7 2 3 |8 5 4 |1 6 9
1 6 4 |3 7 9 |5 2 8
------+------+------
9 8 6 |1 4 7 |3 5 2
3 7 5 |2 6 8 |9 1 4
2 4 1 |5 9 3 |7 8 6
------+------+------
4 3 2 |9 8 1 |6 7 5
6 1 7 |4 2 5 |8 9 3
5 9 8 |7 3 6 |2 4 1
Elapsed milliseconds = 8 ms
All puzzles in sudoku17 (http://staffhome.ecm.uwa.edu.au/~00013890/sudoku17)
Puzzles:49151, Total:80.99 s, Average:1.65 ms</pre>
===SLPsolve===
<syntaxhighlight lang="fsharp">
// 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,014 ⟶ 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:
<pre>
Line 4,029 ⟶ 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,048 ⟶ 4,551:
=={{header|Forth}}==
{{works with|4tH|3.60.0}}
<
include lib/istype.4th
include lib/argopen.4th
Line 4,411 ⟶ 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 4,513 ⟶ 5,016:
end subroutine pretty_print
end program sudoku</
{{out}}<pre>
+-----+-----+-----+
Line 4,546 ⟶ 5,049:
=={{header|FreeBASIC}}==
{{trans|VBA}}
<
Function isSafe(i As Integer, j As Integer, n As Integer) As Boolean
Line 4,632 ⟶ 5,135:
If (i Mod 3 = 0) Then Print !"\n---------+---------+---------" Else Print
Next i
Sleep</
{{out}}
<pre>
Line 4,654 ⟶ 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 4,744 ⟶ 5,244:
toolbox fn print_sudoku() = CFMutableStringRef
gC = " "
Line 4,756 ⟶ 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 4,795 ⟶ 5,297:
More code in this one, but faster execution:
<pre>
begin globals
_digits = 9
Line 4,806 ⟶ 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,168 ⟶ 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,179 ⟶ 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,225 ⟶ 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,426 ⟶ 5,902:
}
c.r.l, c.l.r = &c.x, &c.x
}</
{{out}}
<pre>
Line 5,459 ⟶ 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,473 ⟶ 5,949:
~]{:@0?:^~!{@p}*10,@9/^9/=-@^9%>9%-@3/^9%3/>3%3/^27/={+}*-{@^<\+@1^+>+}/1}do
</syntaxhighlight>
=={{header|Groovy}}==
Line 5,481 ⟶ 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 5,548 ⟶ 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 5,615 ⟶ 6,091:
solution.each { println it }
println "\nELAPSED: ${elapsed} seconds"
}</
{{out}} (last only):
Line 5,649 ⟶ 6,125:
=={{header|Java}}==
<
{
private int mBoard[][];
Line 5,767 ⟶ 6,243:
}
}
}</
{{out}}
Line 5,806 ⟶ 6,282:
====ES6====
<
/**
* The doubly-doubly circularly linked data object.
Line 6,079 ⟶ 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,106 ⟶ 6,582:
let s = new Array(Math.pow(n, 4)).fill('.').join('');
reduceGrid(s);
</syntaxhighlight>
<pre>+-------+-------+-------+
Line 6,135 ⟶ 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,161 ⟶ 6,818:
for i in 1:81
if grid[i] == 0
t = Dict{Int64,
for j in 1:81
Line 6,204 ⟶ 6,861:
0, 5, 0, 6, 9, 0, 0, 1, 0]
solve_sudoku(display, grid)</
{{out}}
<pre>
Line 6,222 ⟶ 6,879:
=={{header|Kotlin}}==
{{trans|C++}}
<
class Sudoku(rows: List<String>) {
Line 6,305 ⟶ 6,962:
)
Sudoku(rows).solve()
}</
{{out}}
Line 6,340 ⟶ 6,997:
=={{header|Lua}}==
===without FFI, slow===
<
--based on a branch and bound solution
--fields are not tried in plain order
Line 6,522 ⟶ 7,179:
if x then
return printer(x)
end</
Input:
<pre>
Line 6,554 ⟶ 7,211:
Time with luajit: 9.245s
===with FFI, fast===
<
ffi=require"ffi"
local printf=function(fmt, ...) io.write(string.format(fmt, ...)) end
Line 6,622 ⟶ 7,279:
... .8. .79
]])
end</
{{out}}
<pre>> time ./sudoku_fast.lua
Line 6,641 ⟶ 7,298:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
NestWhile[
Join @@ Table[
Line 6,650 ⟶ 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 6,660 ⟶ 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 6,671 ⟶ 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,023 ⟶ 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,034 ⟶ 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,046 ⟶ 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,124 ⟶ 7,781:
var puzzle = Sudoku()
puzzle.init(rows)
puzzle.solve()</
{{out}}
Line 7,157 ⟶ 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,226 ⟶ 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,313 ⟶ 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,388 ⟶ 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,420 ⟶ 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 7,676 ⟶ 8,333:
Outfield(solF);
writeln(86400*1000*(T1-T0)/k:10:3,' ms Test calls :',callCnt/k:8:0);
end.</
{{out}}
<pre>
Line 7,712 ⟶ 8,369:
=={{header|Perl}}==
<
use integer;
use strict;
Line 7,751 ⟶ 8,408:
}
}
solve();</
{{out}}
<pre>
Line 7,769 ⟶ 8,426:
=={{header|Phix}}==
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: #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;">"""
..
..
.
.7.
1.
.2....6..
4..7....."""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">valid_move</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">y</span> <span style="color: #0000FF;">-=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">x</span> <span style="color: #0000FF;">-=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">ys</span><span style="color: #0000FF;">=</span><span style="color: #000000;">y</span> <span style="color: #008080;">to</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">xs</span><span style="color: #0000FF;">=</span><span style="color: #000000;">x</span> <span style="color: #008080;">to</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ys</span><span style="color: #0000FF;">][</span><span style="color: #000000;">xs</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">solution</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">brute_solve</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">][</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]<=</span><span style="color: #008000;">'0'</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'1'</span> <span style="color: #008080;">to</span> <span style="color: #008000;">'9'</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">valid_move</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">][</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span>
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">][</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">solution</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (already solved case)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 7,836 ⟶ 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).
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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
-- just wanted to simplify the final display, but later I realised that a 9x9 grid
-- encourages laborious indexing/looping everwhere whereas using a flat 81-element
-- approach encourages precomputation of index sets, and once you commit to that,
-- the rest of the code starts to get a whole lot cleaner. Below we create 27+18
-- sets and 5 tables of lookup indexes to locate them quickly.</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">nines</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000080;font-style:italic;">-- will be 27 in total</span>
<span style="color: #000000;">cols</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- remainder(i-1,9)+1</span>
<span style="color: #000000;">rows</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- floor((i-1)/9)+10</span>
<span style="color: #000000;">squares</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">sixes</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000080;font-style:italic;">-- will be 18 in total</span>
<span style="color: #000000;">dotcol</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- same col, diff square</span>
<span style="color: #000000;">dotrow</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- same row, diff square</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">set_nines</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">nine</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">six</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ndx</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- columns</span>
<span style="color: #000000;">nine</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #000000;">ndx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nines</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">81</span> <span style="color: #008080;">by</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">x</span>
<span style="color: #000000;">nine</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nine</span><span style="color: #0000FF;">,</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">cols</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ndx</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">nines</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nines</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nine</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">81</span> <span style="color: #008080;">by</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- rows</span>
<span style="color: #000000;">nine</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #000000;">ndx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nines</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">x</span>
<span style="color: #000000;">nine</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nine</span><span style="color: #0000FF;">,</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">rows</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ndx</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">nines</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nines</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nine</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nines</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">18</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">by</span> <span style="color: #000000;">3</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- small squares [19..27]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">by</span> <span style="color: #000000;">3</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">nine</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #000000;">ndx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nines</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">sy</span><span style="color: #0000FF;">=</span><span style="color: #000000;">y</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span> <span style="color: #008080;">to</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span><span style="color: #0000FF;">+</span><span style="color: #000000;">18</span> <span style="color: #008080;">by</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">sx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">x</span> <span style="color: #008080;">to</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sy</span><span style="color: #0000FF;">+</span><span style="color: #000000;">sx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">nine</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nine</span><span style="color: #0000FF;">,</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">squares</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ndx</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">nines</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nines</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nine</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nines</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">27</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">six</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #000000;">nine</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cols</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]]</span> <span style="color: #000080;font-style:italic;">-- dotcol</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nine</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">squares</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">squares</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nine</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">six</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">six</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nine</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">ndx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">six</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sixes</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ndx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">sixes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sixes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">six</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">ndx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sixes</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">dotcol</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ndx</span>
<span style="color: #000000;">six</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #000000;">nine</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rows</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]]</span> <span style="color: #000080;font-style:italic;">-- dotrow</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nine</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">squares</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">squares</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nine</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">six</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">six</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nine</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">ndx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">six</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sixes</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ndx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">sixes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sixes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">six</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">ndx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sixes</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">dotrow</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ndx</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">set_nines</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">improved</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">eliminate_in</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">valid</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">..</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #000000;">improved</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">valid</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">test_comb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pool</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">valid</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- (see deep_logic()/set elimination)
-- chosen is a sequence of length 2..4 of integers 1..9: ordered elements of pool.
-- pool is a set of elements of the sequence valid, each of which is a sequence.
-- (note that elements of valid in pool not in chosen are not necessarily sequences)
--</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">contains</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ccount</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ch</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">set</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">set</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pool</span><span style="color: #0000FF;">[</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]]]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'0'</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">contains</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">contains</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">ccount</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ccount</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pool</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">set</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pool</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]]</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- (reverse order so deletions don't foul indexes)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'0'</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">contains</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pool</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">..</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #000000;">improved</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">valid</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #000080;font-style:italic;">-- from [[Combinations#Phix|Combinations]]
-- from http://rosettacode.org/wiki/Combinations#Phix</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">pool</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">valid</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">needed</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">done</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">={})</span>
<span style="color: #000080;font-style:italic;">-- (used by deep_logic()/set elimination)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">needed</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- got a full set</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">test_comb</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pool</span><span style="color: #0000FF;">,</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">done</span><span style="color: #0000FF;">+</span><span style="color: #000000;">needed</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pool</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">valid</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- cannot fulfil
-- get all combinations with and without the next item:</span>
<span style="color: #000000;">done</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pool</span><span style="color: #0000FF;">[</span><span style="color: #000000;">done</span><span style="color: #0000FF;">]])</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pool</span><span style="color: #0000FF;">,</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">needed</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">done</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">),</span><span style="color: #000000;">done</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pool</span><span style="color: #0000FF;">,</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">needed</span><span style="color: #0000FF;">,</span><span style="color: #000000;">done</span><span style="color: #0000FF;">,</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">deep_logic</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">valid</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- Create a grid of valid moves. Note this does not modify board, but instead creates
-- sets of permitted values for each cell, which can also be and are used for hints.
-- Apply standard eliminations of known cells, then try some more advanced tactics:
--
-- 1) row/col elimination
-- If in any of the 9 small squares a number can only occur in one row or column,
-- then that number cannot occur in that row or column in two other corresponding
-- small squares. Example (this one with significant practical benefit):
--
--
--
--
--
--
--
--
--
-- 003|000|200
-- 600|000|000 <-- 3
--
--
-- mid-bottom leads us to eliminating 3s in column 9 and row 9, leaving 7,7 as the
-- only square in the br that can be a 3. Uses dotcol and dotrow.
-- Without this, brute force on the above takes ~8s, but with it ~0s
--
-- 2) set elimination
-- If in any 9-set there is a set of n blank squares that can only contain n digits,
-- then no other squares can contain those digits. Example (with some benefit):
--
--
-- 4.
--
--
-- .
--
--
--
--
-- 84.|.3.|.79
-- The
-- in
-- (
--
-- it spends almost all of its time looking in a completely different place.)
-- (One
-- therefore we should eliminate all non-{5,6} from those squares, as an alternative
-- strategy. However I think that would be harder to code and cannot imagine a case
-- said complementary logic covers, that the above does not, cmiiw.)
--
-- 3) x-wings
-- If a pair of rows or columns can
-- then once filled they will occupy opposite diagonal corners, hence that said number
-- cannot occur elsewhere in those two columns/rows. Example (with a benefit):
-- .43|98.|25. <--
--
--
--
-- 9..|..4|.7. <--
--
--
--
--
-- ...|.4.|..5 <-- hence 6 not in [8,6]
--
-- A
-- (we also eliminate 6 from [4,9], [7,6] and [8,6] to no great use)
-- In practice this offers little benefit over a single trial-and-error step, as
-- obviously trying either 6 in row 1 or 9 immediately pinpoints that 9 anyway.
--
-- 4) swordfish (not attempted)
-- There is an extension to x-wings known as swordfish: three (or more) pairs form
-- a staggered pair (or more) of rectangles that exhibit similar properties, eg:
-- 8-1|-5-
--
-- -
--
-- 6--|9-
--
-- 3*-
-- -
--
-- --8|37-|--9
-- -3-|82-|1--
-- ^---^---^-- 3 pairs of 9s (marked with *) on 3 rows (only)
--
-- Logically you can extend this to N pairs on N rows, however I cannot imagine a
--
-- (eg above if you try [3,5]:=9 it is quickly proved to be invalid, and the same
-- goes for [6,8]:=9 and [7,2]:=9, since they are all entirely inter-dependent.)
--
-- Likewise there are "Alternate Pairs" and "Hook or X-Y wing" strategies, which
-- are easily solved with a single trial-and-error step, and of course the brute
-- force algorithm is going to select pairs first anyway. [Erm, no it doesn't,
-- it selects shortest - I've noted the possible improvement below.]
--</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #000080;font-style:italic;">-- (scratch)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- initialise/start again from scratch</span>
<span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"123456789"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">--
-- First perform standard eliminations of any known cells:
-- (repeated every time so plain_logic() does not have to worry about it)
--</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">></span><span style="color: #008000;">'0'</span>
<span style="color: #008080;">and</span> <span style="color: #004080;">string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span>
<span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">eliminate_in</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cols</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]],</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">eliminate_in</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rows</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]],</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">eliminate_in</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">squares</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]],</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">--
-- 1) row/col elimination
--</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">=</span><span style="color: #000000;">19</span> <span style="color: #008080;">to</span> <span style="color: #000000;">27</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- 0 = none seen, 1..9 this col only, -1: >1 col</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- "" row row</span>
<span style="color: #000000;">nine</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ch</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nine</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">vk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vk</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vk</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">vk</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'0'</span>
<span style="color: #000000;">col</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dotcol</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">row</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dotrow</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">],{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">col</span><span style="color: #0000FF;">})!=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">?</span><span style="color: #000000;">col</span><span style="color: #0000FF;">:-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">],{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">row</span><span style="color: #0000FF;">})!=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">?</span><span style="color: #000000;">row</span><span style="color: #0000FF;">:-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'0'</span>
<span style="color: #000000;">col</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">eliminate_in</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sixes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">col</span><span style="color: #0000FF;">],</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">row</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">eliminate_in</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sixes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">row</span><span style="color: #0000FF;">],</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">--
-- 2) set elimination
--
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nines</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">--
-- Practical note: Meticulously counting empties to eliminate larger set sizes
-- would at best reduce 6642 tests to 972, not deemed worth it.
--</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">set_size</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">4</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">--if floor(count_empties(nines[i])/2)>=set_size then -- (untested)</span>
<span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">set_size</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--end if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">--
-- 3) x-wings
--
<span style="color: #008080;">for</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'1'</span> <span style="color: #008080;">to</span> <span style="color: #008000;">'9'</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">prevsets</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">set</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">idx</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">set</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span><span style="color: #0000FF;">+</span><span style="color: #000000;">x</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prevsets</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">sx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sx</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">k</span> <span style="color: #008080;">and</span> <span style="color: #000000;">sx</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">x</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">eliminate_in</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">y</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span><span style="color: #0000FF;">+</span><span style="color: #000000;">sx</span><span style="color: #0000FF;">},</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">prevsets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">set</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">prevsets</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">set</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span><span style="color: #0000FF;">+</span><span style="color: #000000;">x</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prevsets</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">sy</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sy</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">k</span> <span style="color: #008080;">and</span> <span style="color: #000000;">sy</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">y</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">eliminate_in</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">sy</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span><span style="color: #0000FF;">+</span><span style="color: #000000;">x</span><span style="color: #0000FF;">},</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">prevsets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">set</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">valid</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">permitted_in</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">sets</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">valid</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">set</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">bch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">bch</span><span style="color: #0000FF;">></span><span style="color: #008000;">'0'</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">bch</span><span style="color: #0000FF;">=</span><span style="color: #000000;">ch</span> <span style="color: #008080;">then</span> <span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">elsif</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">idx</span>
<span
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span>
<span style="color: #000000;">improved</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">board</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">INVALID</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">INCOMPLETE</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">SOLVED</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">MULTIPLE</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">BRUTE</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">plain_logic</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- Responsible for:
-- 1) cells with only one option
-- 2) numbers with only one home
--</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">solved</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">solved</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">SOLVED</span>
<span style="color: #000000;">improved</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">deep_logic</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- 1) cells with only one option:</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">vi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vi</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vi</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,{},</span><span style="color: #000000;">INVALID</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vi</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">vi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">improved</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]<=</span><span style="color: #008000;">'0'</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">solved</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">INCOMPLETE</span>
<span style="color:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">solved</span><span style="color: #0000FF;">=</span><span style="color: #000000;">SOLVED</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,{},</span><span style="color: #000000;">SOLVED</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">-- 2) numbers with only one home</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'1'</span> <span style="color: #008080;">to</span> <span style="color: #008000;">'9'</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">permitted_in</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cols</span><span style="color: #0000FF;">,</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">permitted_in</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rows</span><span style="color: #0000FF;">,</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">permitted_in</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,</span><span style="color: #000000;">squares</span><span style="color: #0000FF;">,</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">improved</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">solved</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">validate</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- (sum9 should be sufficient - if you want, get rid of nine/nines)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sum9</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">nine</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nines</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- columns</span>
<span style="color: #000000;">sum9</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">nine</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">81</span> <span style="color: #008080;">by</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'0'</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;"><</span><span style="color: #000000;">1</span> <span style="color: #008080;">or</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">></span><span style="color: #000000;">9</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">sum9</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">ch</span>
<span style="color: #000000;">nine</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sum9</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">45</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nine</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">nines</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">81</span> <span style="color: #008080;">by</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- rows</span>
<span style="color: #000000;">sum9</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">nine</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'0'</span>
<span style="color: #000000;">sum9</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">ch</span>
<span style="color: #000000;">nine</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sum9</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">45</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nine</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">nines</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">by</span> <span style="color: #000000;">3</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- small squares</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">by</span> <span style="color: #000000;">3</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">sum9</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">nine</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">sy</span><span style="color: #0000FF;">=</span><span style="color: #000000;">y</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span> <span style="color: #008080;">to</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span><span style="color: #0000FF;">+</span><span style="color: #000000;">18</span> <span style="color: #008080;">by</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">sx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">x</span> <span style="color: #008080;">to</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sy</span><span style="color: #0000FF;">+</span><span style="color: #000000;">sx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'0'</span>
<span style="color: #000000;">sum9</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">ch</span>
<span style="color: #000000;">nine</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sum9</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">45</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nine</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">nines</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">solution</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">valid</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">solved</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">plain_logic</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">solved</span><span style="color: #0000FF;">=</span><span style="color: #000000;">INVALID</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{{},</span><span style="color: #000000;">INVALID</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">solved</span><span style="color: #0000FF;">=</span><span style="color: #000000;">SOLVED</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">},</span><span style="color: #000000;">SOLVED</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">solved</span><span style="color: #0000FF;">=</span><span style="color: #000000;">BRUTE</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">},</span><span style="color: #000000;">BRUTE</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">solved</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">INCOMPLETE</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">-- find the cell with the fewest options:
-- (a possible improvement here would be to select the shortest
-- with the "most pairs" set, see swordfish etc above.)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">minopt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mindx</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">vi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vi</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vi</span><span style="color: #0000FF;">)<=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- should be caught above</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vi</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">minopt</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">minopt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vi</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">mindx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">solutions</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">minopt</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mindx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mindx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">,</span><span style="color: #000000;">solved</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">solved</span><span style="color: #0000FF;">=</span><span style="color: #000000;">MULTIPLE</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">,</span><span style="color: #000000;">MULTIPLE</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">solved</span><span style="color: #0000FF;">=</span><span style="color: #000000;">SOLVED</span>
<span style="color: #008080;">or</span> <span style="color: #000000;">solved</span><span style="color: #0000FF;">=</span><span style="color: #000000;">BRUTE</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">solutions</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">validate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">solutions</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solutions</span><span style="color: #0000FF;">,</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solutions</span><span style="color: #0000FF;">)></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">solutions</span><span style="color: #0000FF;">,</span><span style="color: #000000;">MULTIPLE</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">elsif</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solutions</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">solutions</span><span style="color: #0000FF;">,</span><span style="color: #000000;">BRUTE</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solutions</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">solutions</span><span style="color: #0000FF;">,</span><span style="color: #000000;">BRUTE</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{{},</span><span style="color: #000000;">INVALID</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">test_one</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">solutions</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">solved</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">solution</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">desc</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">solved</span><span style="color: #0000FF;">=</span><span style="color: #000000;">SOLVED</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">desc</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"(logic)"</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">solved</span><span style="color: #0000FF;">=</span><span style="color: #000000;">BRUTE</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">desc</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"(brute force)"</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">desc</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"???"</span> <span style="color: #000080;font-style:italic;">-- INVALID/INCOMPLETE/MULTIPLE</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solutions</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">solution</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">board</span>
<span style="color: #000000;">desc</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"*** NO SOLUTIONS ***"</span>
<span style="color: #008080;">elsif</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solutions</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">solution</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">solutions</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">validate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">desc</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"*** ERROR ***"</span> <span style="color: #000080;font-style:italic;">-- (should never happen)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">solution</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">board</span>
<span style="color: #000000;">desc</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"*** MULTIPLE SOLUTIONS ***"</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">,</span><span style="color: #000000;">desc</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #000080;font-style:italic;">--NB Blank cells can be represented by any character <'1'. Spaces are not recommended since
-- they can all too easily be converted to tabs by copy/paste/save. In particular, ? and
-- _ are NOT valid characters for representing a blank square. Use any of .0-* instead.</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span>
<span style="color: #008000;">"..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9"</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.01s, (logic))
-- row/col elimination (was 8s w/o logic first)</span>
<span style="color: #008000;">"000000036840000000000000020000203000010000700000600400000410050003000200600000000"</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.04s, (brute force))</span>
<span style="color: #008000;">".......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7....."</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (1.12s, (brute force))</span>
<span style="color: #008000;">"000037600000600090008000004090000001600000009300000040700000800010009000002540000"</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.00s, (logic))</span>
<span style="color: #008000;">"....839..1......3...4....7..42.3....6.......4....7..1..2........8...92.....25...6"</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.04s, (brute force))</span>
<span style="color: #008000;">"..1..5.7.92.6.......8...6...9..2.4.1.........3.4.8..9...7...3.......7.69.1.8..7.."</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.00s, (logic))
-- (the following takes ~8s when checking for multiple solutions)</span>
<span style="color: #008000;">"--3------4---8--36--8---1---4--6--73---9----------2--5--4-7--686--------7--6--5--"</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.01s, (brute force))</span>
<span style="color: #008000;">"..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3.."</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.00s, (logic))</span>
<span style="color: #008000;">"--4-5--6--6-1--8-93----7----8----5-----4-3-----6----7----2----61-5--4-3--2--7-1--"</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.00s, (logic))
-- x-wings</span>
<span style="color: #008000;">".4398.25.6..425...2....1.949....4.7.3..6.8...41.2.9..382.5.........4...553489.71."</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.00s, (logic))</span>
<span style="color: #008000;">".9...4..7.
-- "AL Escargot", so-called "hardest sudoku"</span>
<span style="color: #008000;">"1....
<span style="color: #008000;">"12.3.
<span style="color: #008000;">"12.4..3..3...1..5...6...1..7...9.....4.6.3.....3..2...5...8.7....7.....5.......98"</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (1.07s, (brute force))</span>
<span style="color: #008000;">"394..267....3..4..5..69..2..45...9..6.......7..7...58..1..67..8..9..8....264..735"</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.00s, (logic))</span>
<span style="color: #008000;">"4....
<span style="color: #008000;">"5...7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79"</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.00s, (logic))</span>
<span style="color: #008000;">"503600009010002600900000080000700005006804100200003000030000008004300050800006702"</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.00s, (logic))</span>
<span style="color: #008000;">"53.
<span style="color: #008000;">"530070000600195000098000060800060003400803001700020006060000280000419005000080079"</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.00s, (logic))
-- set exclusion</span>
<span style="
-- Worlds hardest sudoku:</span>
<span style="color: #008000;">"800000000003600000070090200050007000000045700000100030001000068008500010090000400"</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.21s, (brute force))</span>
<span style="color: #008000;">"819--5-----2---75--371-4-6-4--59-1--7--3-8--2--3-62--7-5-7-921--64---9-----2--438"</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.00s, (logic))</span>
<span style="
<span style="
<span style="color: #008000;">"97.3...6..6.75.........8.5.......67.....3.....539..2..7...25.....2.1...8.4...73.."</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.00s, (logic))
-- "the beast" (an earlier algorithm took 318s (5min 18s) on this):</span>
<span style="color: #008000;">"000060080020000000001000000070000102500030000000000400004201000300700600000000050"</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (0.03s, (brute force))</span>
<span style="color: #0000FF;">$},</span>
<span style="color: #000000;">lt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">run_one_test</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">" x x x | x x x | x x x "</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"-------+-------+-------"</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">l3</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">({</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">},</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">fmt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">substitute</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">({</span><span style="color: #000000;">l3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l3</span><span style="color: #0000FF;">},</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"x"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%c"</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"\n"</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (81 characters)</span>
<span style="color: #000000;">solution</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">desc</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">run_one_test</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">run_one_test</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: #000000;">fmt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">board</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">,</span><span style="color: #000000;">desc</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">test_one</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</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;">"solution:\n"</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: #000000;">fmt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</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, %3.2fs\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">desc</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: #008080;">else</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lt</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">,</span><span style="color: #000000;">desc</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">test_one</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</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\", -- (%3.2fs, %s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">desc</span><span style="color: #0000FF;">})</span>
<span style="color: #000080;font-style:italic;">-- printf(1," \"%s\", -- (%3.2fs, %s)\n",{solution,time()-t1,desc})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">t0</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: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d puzzles solved in %3.2fs (av %3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">lt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">/</span><span style="color: #000000;">lt</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 8,562 ⟶ 9,209:
=={{header|PHP}}==
{{trans|C++}}
<
protected $grid = [];
protected $emptySymbol;
Line 8,686 ⟶ 9,333:
$solver = new SudokuSolver('009170000020600001800200000200006053000051009005040080040000700006000320700003900');
$solver->solve();
$solver->display();</
{{out}}
<pre>
Line 8,701 ⟶ 9,348:
7 8 2 | 5 6 3 | 9 1 4
(solved in 0.027s)
</pre>
=={{header|Picat}}==
Using constraint programming.
<syntaxhighlight lang="picat">import util.
import cp.
main => go.
go =>
sudokus(Sudokus),
foreach([Comment,SudokuS] in Sudokus)
println(SudokuS),
println(Comment),
% Convert string to numbers and "." to _ (unknown)
Sudoku = [ [cond(S == '.',_,S.to_integer()) :
S in slice(SudokuS,(I*9)+1,(I+1)*9)] : I in 0..8],
print_board(Sudoku),
% Ensure unicity of the solution (check that it is a unique solution)
All = findall(Sudoku,sudoku(Sudoku)),
if All.length > 1 then
printf("Problem has %d solutions!\n", All.length)
end,
print("Solution:")
foreach(A in All)
print_board(A)
end,
nl
end,
nl.
sudoku(Board) =>
N = ceiling(sqrt(Board.len)),
N2 = N*N,
Vars = Board.vars(),
Vars :: 1..N2,
foreach(Row in Board) all_different(Row) end,
foreach(Column in transpose(Board)) all_different(Column) end,
foreach(I in 1..N..N2, J in 1..N..N2)
all_different([Board[I+K,J+L] : K in 0..N-1, L in 0..N-1])
end,
solve([ffd,inout], Vars).
print_board(Board) =>
N = Board.length,
foreach(I in 1..N)
foreach(J in 1..N)
X = Board[I,J],
if var(X) then printf(" _") else printf(" %w", X) end
end,
nl
end,
nl.
% (Problems from the Groovy implementation)
sudokus(Sudokus) => Sudokus =
[
"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.",
"..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..",
"394..267....3..4..5..69..2..45...9..6.......7..7...58..1..67..8..9..8....264..735",
"97.3...6..6.75.........8.5.......67.....3.....539..2..7...25.....2.1...8.4...73..",
"4......6.5...8.9..3....1....2.7....1.9.....4.8....3.5....2....7..6.5...8.1......6",
"85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.",
"..1..5.7.92.6.......8...6...9..2.4.1.........3.4.8..9...7...3.......7.69.1.8..7..",
".9...4..7.....79..8........4.58.....3.......2.....97.6........4..35.....2..6...8.",
"12.3....435....1....4........54..2..6...7.........8.9...31..5.......9.7.....6...8",
"9..2..5...4..6..3...3.....6...9..2......5..8...7..4..37.....1...5..2..4...1..6..9",
"1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..",
"12.4..3..3...1..5...6...1..7...9.....4.6.3.....3..2...5...8.7....7.....5.......98",
"..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9",
".......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....",
"....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
8 1 9 _ _ 5 _ _ _
_ _ 2 _ _ _ 7 5 _
_ 3 7 1 _ 4 _ 6 _
4 _ _ 5 9 _ 1 _ _
7 _ _ 3 _ 8 _ _ 2
_ _ 3 _ 6 2 _ _ 7
_ 5 _ 7 _ 9 2 1 _
_ 6 4 _ _ _ 9 _ _
_ _ _ 2 _ _ 4 3 8
Solution:
8 1 9 6 7 5 3 2 4
6 4 2 9 8 3 7 5 1
5 3 7 1 2 4 8 6 9
4 2 6 5 9 7 1 8 3
7 9 5 3 1 8 6 4 2
1 8 3 4 6 2 5 9 7
3 5 8 7 4 9 2 1 6
2 6 4 8 3 1 9 7 5
9 7 1 2 5 6 4 3 8
...
</pre>
=={{header|PicoLisp}}==
<
### Fields/Board ###
Line 8,785 ⟶ 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 8,807 ⟶ 9,558:
+---+---+---+---+---+---+---+---+---+
a b c d e f g h i</pre>
<syntaxhighlight lang
{{out}}
<pre> +---+---+---+---+---+---+---+---+---+
Line 8,832 ⟶ 9,583:
=={{header|PL/I}}==
Working PL/I version, derived from the Rosetta Fortran version.
<
declare grid (9,9) fixed (1) static initial (
Line 8,915 ⟶ 9,666:
end sudoku;
</syntaxhighlight>
{{out}}
<pre>
Line 8,949 ⟶ 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,088 ⟶ 9,839:
end sudoku;
</syntaxhighlight>
=={{header|Prolog}}==
<
sudoku(Rows) :-
Line 9,116 ⟶ 9,867:
[5,_,_,_,_,_,_,7,3],
[_,_,2,_,1,_,_,_,_],
[_,_,_,_,4,_,_,_,9]]).</
===GNU Prolog version===
{{works with|GNU Prolog|1.4.4}}
<
Line 9,173 ⟶ 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,188 ⟶ 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,298 ⟶ 10,049:
Input()
CloseConsole()
EndIf</
{{out}}
<pre>+-----+-----+-----+
Line 9,330 ⟶ 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 9,416 ⟶ 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 9,425 ⟶ 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 9,465 ⟶ 10,285:
}
}
solve;</
{{out}}
Line 9,483 ⟶ 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 9,704 ⟶ 10,524:
}
}
}</
{{out}}
Line 9,722 ⟶ 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 9,805 ⟶ 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,098 ⟶ 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,188 ⟶ 11,008:
print_matrix(matrix)
puts
print_matrix(solve_sudoku(matrix))</
{{out}}
Line 10,222 ⟶ 11,042:
=={{header|Rust}}==
{{trans|Ada}}
<
fn is_valid(val: u8, x: usize, y: usize, sudoku_ar: &mut Sudoku) -> bool {
Line 10,285 ⟶ 11,105:
println!("Unsolvable");
}
}</
{{out}}
Line 10,307 ⟶ 11,127:
Use CLP solver in SAS/OR:
<
data Indata;
input C1-C9;
Line 10,353 ⟶ 11,173:
/* print solution */
print X;
quit;</
Output:
Line 10,374 ⟶ 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 10,505 ⟶ 11,325:
println(solution match {case Nil => "no solution!!!" case _ => f2Str(solution)})
}</
{{out}}
<pre>riddle:
Line 10,539 ⟶ 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 10,656 ⟶ 11,476:
+("\n"*2))
}
}</
{{out}}
<pre>riddle used in Ada section:
Line 10,787 ⟶ 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 10,959 ⟶ 11,779:
disp('Invalid solution found.');
disp_board(Solved_board);
end</
{{out}}
Line 11,019 ⟶ 11,839:
=={{header|Sidef}}==
{{trans|Raku}}
<
var (id, im) = i.divmod(9)
var (jd, jm) = j.divmod(9)
Line 11,067 ⟶ 11,887:
)
solve(grid)</
{{out}}
<pre>5 3 9 8 2 4 7 6 1
Line 11,082 ⟶ 11,902:
=={{header|Shale}}==
<
#!/usr/local/bin/shale
Line 11,612 ⟶ 12,432:
// I'd like to see an irregular sudoku with a knight's move constraint. Any takers...
</syntaxhighlight>
'''Output'''
Line 11,653 ⟶ 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 11,681 ⟶ 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 11,705 ⟶ 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 11,805 ⟶ 12,625:
sudoku(a)
a
end</
'''Output'''
Line 11,826 ⟶ 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 11,878 ⟶ 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,005 ⟶ 12,825:
let puzzle = Soduku(board: board)
puzzle.solve()
puzzle.printBoard()</
{{out}}
<pre>
Line 12,025 ⟶ 12,845:
{{works with|Swift 3}}
<syntaxhighlight lang="swift">
func solving(board: [[Int]]) -> [[Int]] {
var board = board
Line 12,090 ⟶ 12,910:
print(solving(board: puzzle))
</syntaxhighlight>
{{out}}
<pre>
Line 12,109 ⟶ 12,929:
<
//////////////////////////////////////////////////////////////////////////////
Line 12,239 ⟶ 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,294 ⟶ 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,309 ⟶ 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,399 ⟶ 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 12,441 ⟶ 13,261:
'> 'solves sudoku and outputs pretty solution'
end 'sudoku solver'
</syntaxhighlight>
=={{header|Tcl}}==
Line 12,448 ⟶ 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 12,696 ⟶ 13,516:
return 0
}
}</
Demonstration code:
<
sudoku load {
{3 9 4 @ @ 2 6 7 @}
Line 12,721 ⟶ 13,541:
}
}
sudoku destroy</
{{out}}
<pre>+-----+-----+-----+
Line 12,737 ⟶ 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 12,790 ⟶ 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 12,803 ⟶ 13,668:
~&rgg&& ~&irtPFXlrjrXPS; ~&lrK2tkZ2g&& ~&llrSL2rDrlPrrPljXSPTSL)+-,
//~&p ^|DlrDSLlrlPXrrPDSL(~&,num*+ rep2 block3)*= num block27 ~&iiK0 iota9,
* `0?=\~&iNC ! ~&t digits+-</
test program:
<
example =
Line 12,820 ⟶ 13,685:
010067008
009008000
026400735]-</
{{out}}
<pre>
Line 12,838 ⟶ 13,703:
=={{header|VBA}}==
{{trans|Fortran}}
<
Dim gridSolved(9, 9)
Line 12,939 ⟶ 13,804:
Debug.Print
Next i
End Sub</
{{out}}
<pre>
Line 12,958 ⟶ 13,823:
{{trans|VBA}}
To run in console mode with cscript.
<
Dim gridSolved(9, 9)
Line 13,059 ⟶ 13,924:
End Sub 'Sudoku
Call sudoku</
{{out}}
<pre>Problem:
Line 13,081 ⟶ 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,161 ⟶ 14,184:
"000036040"
]
Sudoku.new(rows).solve()</
{{out}}
Line 13,198 ⟶ 14,221:
can be verified by several other examples.
{{trans|C}}
<
proc Show(X);
Line 13,268 ⟶ 14,291:
..9 ..8 ...
.26 4.. 735 ");
]</
{{out}}
Line 13,287 ⟶ 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,308 ⟶ 14,331:
sdku[pos]=0;
return(False);
}</
<
#<<<
" 5 3 0 0 7 0 0 0 0
Line 13,327 ⟶ 14,350:
s[n*27,27].pump(Console.println,T(Void.Read,8),("| " + "%s%s%s | "*3).fmt); // 3 lines
println("+-----+-----+-----+");
}</
{{out}}
<pre>
|