Sudoku: Difference between revisions

(62 intermediate revisions by 14 users not shown)

Line 12:

<~~lang~~ 11l>T Sudoku

<syntaxhighlight lang="11l">T Sudoku

solved = 0B

grid = [0] * 81

Line 83:

‘000036040’]

Sudoku(rows).solve()</~~lang~~>

Sudoku(rows).solve()</syntaxhighlight>

Line 118:

=={{header|8th}}==

<~~lang~~ 8th>

\

\ Simple iterative backtracking Sudoku solver for 8th

Line 265:

"No solution!\n" .

then ;

</syntaxhighlight>

</lang>

=={{header|Ada}}==

<~~lang~~ ada>

with Ada.Text_IO;

Line 378:

solve( sudoku_ar );

end Sudoku;

</syntaxhighlight>

</lang>

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''.}}

<~~lang~~ algol68>MODE AVAIL = [9]BOOL;

<syntaxhighlight lang="algol68">MODE AVAIL = [9]BOOL;

MODE BOX = [3, 3]CHAR;

Line 495:

"__1__6__9"))

END CO

)</~~lang~~>

)</syntaxhighlight>

<pre>

Line 515:

=={{header|AutoHotkey}}==

<~~lang~~ ~~AutoHotkey~~>#SingleInstance, Force

<syntaxhighlight lang="autohotkey">#SingleInstance, Force

SetBatchLines, -1

SetTitleMatchMode, 3

Line 658:

r .= SubStr(p, A_Index, 1) . "|"

return r

}</~~lang~~>

}</syntaxhighlight>

=={{header|AWK}}==

# syntax: GAWK -f SUDOKU_RC.AWK

BEGIN {

Line 849:

}

function error(message) { printf("error: %s\n",message) ; errors++ }

</syntaxhighlight>

</lang>

<pre>

Line 886:

[[Image:sudoku_bbc.gif|right]]

<~~lang~~ bbcbasic> VDU 23,22,453;453;8,20,16,128

<syntaxhighlight lang="bbcbasic"> VDU 23,22,453;453;8,20,16,128

*FONT Arial,28

Line 990:

ENDIF

= D%</~~lang~~>

= D%</syntaxhighlight>

=={{header|BCPL}}==

<~~lang~~ ~~BCPL~~>// This can be run using Cintcode BCPL freely available from www.cl.cam.ac.uk/users/mr10.

<syntaxhighlight lang="bcpl">// This can be run using Cintcode BCPL freely available from www.cl.cam.ac.uk/users/mr10.

// Implemented by Martin Richards.

Line 1,388:

{ count := count + 1

prboard()

}</~~lang~~>

}</syntaxhighlight>

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

<~~lang~~ befunge>99*>1-:0>:#$"0"\# #~`#$_"0"-\::9%:9+00p3/\9/:99++10p3vv%2g\g01<

<syntaxhighlight lang="befunge">99*>1-:0>:#$"0"\# #~`#$_"0"-\::9%:9+00p3/\9/:99++10p3vv%2g\g01<

2%v|:p+9/9\%9:\p\g02\1p\g01\1:p\g00\1:+8:\p02+*93+*3/<>\20g\g#:

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:</~~lang~~>

::>^_:#<0#!:p#-\#1:#g0<>30g010g30g020g30g040g:9%\:9/9+\01-\1+0:</syntaxhighlight>

Line 1,431:

=={{header|Bracmat}}==

The program:

<~~lang~~ bracmat>{sudokuSolver.bra

<syntaxhighlight lang="bracmat">{sudokuSolver.bra

Solves any 9x9 sudoku, using backtracking.

Line 1,619:

. new$((its.sudoku),!arg):?puzzle

& (puzzle..Display)$

);</~~lang~~>

);</syntaxhighlight>

Solve a sudoku that is hard for a brute force solver:

<~~lang~~ bracmat>new'( sudokuSolver

<syntaxhighlight lang="bracmat">new'( sudokuSolver

, (.- - - - - - - - -)

(.- - - - - 3 - 8 5)

Line 1,631:

(.- - 2 - 1 - - - -)

(.- - - - 4 - - - 9)

);</~~lang~~>

);</syntaxhighlight>

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.

<~~lang~~ c>#include <stdio.h>

<syntaxhighlight lang="c">#include <stdio.h>

void show(int *x)

Line 1,717:

return 0;

}</~~lang~~>

}</syntaxhighlight>

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

===Backtracking===

===Simple Backtrack Solution===

<~~lang~~ csharp>using System;

<syntaxhighlight lang="csharp">using System;

class SudokuSolver

Line 1,824:

Console.Read();

}

}</~~lang~~>

}</syntaxhighlight>

=== ~~"Smart"~~ ~~Recursive~~ ~~Backtrack Solution~~===

=== Best First Search===

<~~lang~~ csharp>using System.Linq;

<syntaxhighlight lang="csharp">using System.Linq;

using static System.Linq.Enumerable;

using System.Collections.Generic;

Line 1,834:

using System.Runtime.CompilerServices;

namespace ~~Sudoku~~ {

namespace SodukoFastMemoBFS {

internal ~~static~~ ~~class~~ ~~Sudoku~~ {

internal readonly record struct Square (int Row, int Col);

internal record Constraints (IEnumerable<int> ConstrainedRange, Square Square);

[MethodImpl(MethodImplOptions.AggressiveInlining)]

internal class Cache : Dictionary<Square, Constraints> { };

private static int RowCol(int rc) => rc <= 2 ? 0 : rc <= 5 ? 3 : 6;

internal record CacheGrid (int[][] Grid, Cache Cache);

private static IEnumerable<int> GetBox(this int[][] grid, int row, int col) =>

from r in Range(RowCol(row), 3)

from c in Range(RowCol(col), 3)

select grid[r][c];

internal static class SudokuFastMemoBFS {

private static readonly int[] range = Range(1, 9).ToArray();

~~private~~ static ~~bool~~ ~~Solve~~(this ~~int[][]~~ ~~grid~~, ~~List~~<~~(int~~, ~~int)~~> ~~cells,~~ ~~int~~ ~~idx~~) {

internal static U Fwd<T, U>(this T data, Func<T, U> f) => f(data);

if (idx == 81)

return true;

[MethodImpl(MethodImplOptions.AggressiveInlining)]

var (r, c) = cells[idx];

private static int RowCol(int rc) => rc <= 2 ? 0 : rc <= 5 ? 3 : 6;

foreach (var i in range.Except(grid.Hints(r,c))) {

grid[r][c] = i;

private static bool Solve(this CacheGrid cg, Constraints constraints, int finished) {

if (grid.Solve(cells, idx + 1))

~~return true~~;

var (row, col) = constraints.Square;

foreach (var i in constraints.ConstrainedRange) {

cg.Grid[row][col] = i;

if (cg.Cache.Count == finished || cg.Solve(cg.Next(constraints.Square), finished))

return true;

}

~~grid~~[r][c] = 0;

cg.Grid[row][col] = 0;

return false;

}

private static readonly int[] Unmarked = new[] { 0 };

private static readonly int[] domain = Range(0, 9).ToArray();

private static readonly int[] range = Range(1, 9).ToArray();

private static ~~IEnumerable<int>~~ ~~Hints~~(this int[][] grid, int row, int col) =>

private static bool Valid(this int[][] grid, int row, int col, int val) {

~~grid[row]~~

for (var i = 0; i < 9; i++)

~~.Union(domain.Select~~(r => grid[r][col]))

if (grid[row][i] == val || grid[i][col] == val)

~~.Union(grid.GetBox(row,~~ ~~col))~~

return false;

~~.Except~~(~~Unmarked~~);

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~~, int)~~> ~~SortedCells~~(this int[][] grid) =>

private static IEnumerable<int> Constraints(this int[][] grid, int row, int col) =>

~~from~~ row in ~~domain~~

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

~~let cell = (count:~~ grid[row][col] > 0 ~~? 10 : grid.Hints(row, col).Count(), cell: (row, col))~~

where grid[row][col] == 0

let cell = new Constraints(grid.Constraints(row, col), new Square(row, col))

orderby cell.count descending

~~select~~ cell.~~cell;~~

orderby cell.ConstrainedRange.Count() ascending

select cell).First();

private static ~~int[][]~~ Parse(string input) =>

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();

.ToArray()

.Fwd(grid => new CacheGrid(grid, new Cache()));

public static string AsString(this int[][] grid) =>

string.Join('\n', grid.Select(row => string.Concat(row)));

public static int[][] Run(string input) {

var ~~grid~~ = Parse(input);

var cg = Parse(input);

var ~~hits~~ = ~~input~~.Where(c => c != '0').Count();

var marked = cg.Grid.SelectMany(row => row.Where(c => c > 0)).Count();

~~var~~ ~~sorted = grid~~.SortedCells().~~ToList~~();

return cg.Solve(cg.Grid.SortedCells(), 80 - marked) ? cg.Grid : new int[][] { Array.Empty<int>() };

return grid.Solve(sorted, hits) ? grid : new int[][] { Array.Empty<int>() };

}

}</~~lang~~>

}</syntaxhighlight>

Usage

<syntaxhighlight lang="csharp">using System.Linq;

using static System.Linq.Enumerable;

using static System.Console;

using System.IO;

namespace Sudoku {

static class Program {

namespace SodukoFastMemoBFS {

static void Main(string[] args) {

static class Program {

//https://staffhome.ecm.uwa.edu.au/~00013890/sudoku17 format

var puzzle = "000028000800010000000000700000600403200004000100700000030400500000000010060000000";

static void Main(string[] args) {

WriteLine(Sudoku.Run(puzzle).AsString());

~~Read~~();

var num = int.Parse(args[0]);

var puzzles = File.ReadLines(@"sudoku17.txt").Take(num);

}

var single = puzzles.First();

}

}</lang>

var watch = new System.Diagnostics.Stopwatch();

watch.Start();

WriteLine(SudokuFastMemoBFS.Run(single).AsString());

watch.Stop();

WriteLine($"{single}: {watch.ElapsedMilliseconds} ms");

WriteLine($"Doing {num} puzzles");

var total = 0.0;

watch.Start();

foreach (var puzzle in puzzles) {

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>

<pre>693784512

487512936

617328945

125963874

894517236

932651487

325946781

568247391

978651423

741398625

256834179

319475268

143792658

856129743

731489562

274836159

489265317

000000010400000000020000000000050407008000300001090000300400200050100000000806000: 336 ms

562173894

Doing 100 puzzles

</pre>

....................................................................................................

Puzzles:100, Total:5316 ms, Average:53.16 ms</pre>

===Solver===

===“Automatic” Solution===

<~~lang~~ csharp>using Microsoft.SolverFoundation.Solvers;

<syntaxhighlight lang="csharp">using Microsoft.SolverFoundation.Solvers;

namespace Sudoku

Line 1,994:

Line 2,032:

}

}</~~lang~~>

}</syntaxhighlight>

Produces:

<pre>

Line 2,010:

Line 2,048:

</pre>

===~~Using the~~ "Dancing Links" ~~algorithm~~===

==="Dancing Links"/Algorithm X===

<~~lang~~ csharp>using System;

<syntaxhighlight lang="csharp">using System;

using System.Collections.Generic;

using System.Text;

Line 2,289:

Line 2,327:

public static string DelimitWith<T>(this IEnumerable<T> source, string separator) => string.Join(separator, source);

}</~~lang~~>

}</syntaxhighlight>

<pre>

Line 2,314:

Line 2,352:

=={{header|C++}}==

<~~lang~~ cpp>#include <iostream>

<syntaxhighlight lang="cpp">#include <iostream>

using namespace std;

Line 2,405:

Line 2,443:

ss.solve();

return EXIT_SUCCESS;

}</~~lang~~>

}</syntaxhighlight>

=={{header|Clojure}}==

<~~lang~~ clojure>(ns rosettacode.sudoku

<syntaxhighlight lang="clojure">(ns rosettacode.sudoku

(:use [clojure.pprint :only (cl-format)]))

Line 2,431:

Line 2,469:

(if (= x (dec c))

(recur ng 0 (inc y))

(recur ng (inc x) y)))))))</~~lang~~>

(recur ng (inc x) y)))))))</syntaxhighlight>

<~~lang~~ clojure>sudoku>(cl-format true "~{~{~a~^ ~}~%~}"

<syntaxhighlight lang="clojure">sudoku>(cl-format true "~{~{~a~^ ~}~%~}"

(solve [[3 9 4 0 0 2 6 7 0]

[0 0 0 3 0 0 4 0 0]

Line 2,453:

Line 2,491:

8 2 6 4 1 9 7 3 5

nil</~~lang~~>

nil</syntaxhighlight>

=={{header|Common Lisp}}==

A simple solver without optimizations (except for pre-computing the possible entries of a cell).

<~~lang~~ lisp>(defun row-neighbors (row column grid &aux (neighbors '()))

<syntaxhighlight lang="lisp">(defun row-neighbors (row column grid &aux (neighbors '()))

(dotimes (i 9 neighbors)

(let ((x (aref grid row i)))

Line 2,496:

Line 2,534:

(setf (aref grid row column) choice)

(when (eq grid (solve grid row (1+ column)))

(return grid))))))</~~lang~~>

(return grid))))))</syntaxhighlight>

Example:

<pre>> (defparameter *puzzle*

Line 2,523:

Line 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

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

return false

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>

<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].

<~~lang~~ curry>-----------------------------------------------------------------------------

<syntaxhighlight lang="curry">-----------------------------------------------------------------------------

--- Solving Su Doku puzzles in Curry with FD constraints

---

Line 2,588:

Line 2,728:

" 5 7 921 ",

" 64 9 ",

" 2 438"]</~~lang~~>

" 2 438"]</syntaxhighlight>

Line 2,594:

Line 2,734:

Minimal w/o read or show utilities.

<~~lang~~ curry>import CLPFD

<syntaxhighlight lang="curry">import CLPFD

import Constraint (allC)

import List (transpose)

Line 2,627:

Line 2,767:

, [7,_,_,6,_,_,5,_,_]

]

main | sudoku xs = xs where xs = test</~~lang~~>

main | sudoku xs = xs where xs = test</syntaxhighlight>

<pre>Execution time: 0 msec. / elapsed: 10 msec.

Line 2,635:

Line 2,775:

A little over-engineered solution, that shows some strong static typing useful in larger programs.

<~~lang~~ d>import std.stdio, std.range, std.string, std.algorithm, std.array,

<syntaxhighlight lang="d">import std.stdio, std.range, std.string, std.algorithm, std.array,

std.ascii, std.typecons;

Line 2,761:

Line 2,901:

else

solution.get.representSudoku.writeln;

}</~~lang~~>

}</syntaxhighlight>

<pre>8 5 . | . . 2 | 4 . .

Line 2,789:

Line 2,929:

===Short Version===

Adapted from: http://code.activestate.com/recipes/576725-brute-force-sudoku-solver/

<~~lang~~ d>import std.stdio, std.algorithm, std.range;

<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.range;

const(int)[] solve(immutable int[] s) pure nothrow @safe {

Line 2,822:

Line 2,962:

0, 0, 0, 0, 3, 6, 0, 4, 0];

writefln("%(%s\n%)", problem.solve.chunks(9));

}</~~lang~~>

}</syntaxhighlight>

<pre>[8, 5, 9, 6, 1, 2, 4, 3, 7]

Line 2,836:

Line 2,976:

===No-Heap Version===

This version is similar to the precedent one, but it shows idioms to avoid memory allocations on the heap. This is enforced by the use of the @nogc attribute.

<~~lang~~ d>import std.stdio, std.algorithm, std.range, std.typecons;

<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.range, std.typecons;

Nullable!(const ubyte[81]) solve(in ubyte[81] s) pure nothrow @safe @nogc {

Line 2,877:

Line 3,017:

0, 0, 0, 0, 3, 6, 0, 4, 0];

writefln("%(%s\n%)", problem.solve.get[].chunks(9));

}</~~lang~~>

}</syntaxhighlight>

Same output.

=={{header|Delphi}}==

Example taken from C++

<~~lang~~ delphi>type

<syntaxhighlight lang="delphi">type

TIntArray = array of Integer;

Line 3,006:

Line 3,146:

ShowMessage('Solved!');

end;

end;</~~lang~~>

end;</syntaxhighlight>

Usage:

<~~lang~~ delphi>var

<syntaxhighlight lang="delphi">var

SudokuSolver: TSudokuSolver;

begin

Line 3,025:

Line 3,165:

FreeAndNil(SudokuSolver);

end;

end;</~~lang~~>

end;</syntaxhighlight>

=={{header|EasyLang}}==

<lang>len row[] 810

len ~~col~~[] ~~810~~

len row[] 90

len ~~box~~[] ~~810~~

len col[] 90

len box[] 90

len grid[] 82

#

~~func~~ init . .

proc init . .

for pos ~~range~~ 81

for pos = 1 to 81

if pos mod 9 = 0

if pos mod 9 = 1

s$[] = ~~str_split~~ input ~~" "~~

s$ = input

.

if s$ = ""

~~dig~~ = ~~number~~ s$~~[pos~~ ~~mod~~ 9]

s$ = input

~~grid[pos]~~ = ~~dig~~

.

r = ~~pos~~ ~~div~~ 9

len inp[] 0

c = ~~pos~~ ~~mod~~ 9

for i = 1 to len s$

b = r ~~div~~ 3 * 3 + c ~~div~~ 3

if substr s$ i 1 <> " "

~~row[r~~ * 10 + ~~dig~~] = 1

inp[] &= number substr s$ i 1

~~col[c~~ * 10 + ~~dig]~~ = 1

.

~~box[b~~ * 10 + ~~dig]~~ ~~= 1~~

.

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

.

~~call~~ init

init

#

~~func~~ display . .

proc display . .

for i ~~range~~ 81

for i = 1 to 81

write grid[i] & " "

if i mod 3 = 2

if i mod 3 = 0

write " "

.

if i mod 9 = 8

if i mod 9 = 0

print ""

.

if i mod 27 = 26

if i mod 27 = 0

print ""

.

#

~~func~~ solve pos . .

proc solve pos . .

while grid[pos] <> 0

pos += 1

.

if pos = 81

if pos > 81

# solved

~~call~~ display

display

~~break~~ 1

return

.

r = pos div 9

r = (pos - 1) div 9

c = pos mod 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

~~call~~ solve pos + 1

solve pos + 1

row[r + d] = 0

col[c + d] = 0

box[b + d] = 0

.

grid[pos] = 0

.

~~call~~ solve 0

solve 1

#

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 0 8 0 7 2 0 4 9

0 2 0 9 8 0 0 7 0

0 0 8 0 7 2 0 4 9

7 9 0 0 0 0 0 8 0

0 2 0 9 8 0 0 7 0

0 0 0 0 3 0 5 0 6

7 9 0 0 0 0 0 8 0

9 6 0 0 1 0 3 0 0

0 5 0 ~~6 9~~ 0 0 1 0~~</lang>~~

0 0 0 0 3 0 5 0 6

9 6 0 0 1 0 3 0 0

0 5 0 6 9 0 0 1 0

</syntaxhighlight>

=={{header|Elixir}}==

<~~lang~~ elixir>defmodule Sudoku do

<syntaxhighlight lang="elixir">defmodule Sudoku do

def display( grid ), do: ( for y <- 1..9, do: display_row(y, grid) )

Line 3,265:

Line 3,421:

{{3, 8}, 2}, {{5, 8}, 1},

{{5, 9}, 4}, {{9, 9}, 9}]

Sudoku.task( difficult )</~~lang~~>

Sudoku.task( difficult )</syntaxhighlight>

Line 3,325:

Line 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.

-module( sudoku ).

Line 3,488:

Line 3,644:

display( Solved ),

io:nl().

</syntaxhighlight>

</lang>

<pre>

Line 3,572:

Line 3,728:

0 is the empty cell.

!--------------------------------------------------------------------

! risolve Sudoku: in input il file SUDOKU.TXT

Line 3,979:

Line 4,135:

</syntaxhighlight>

</lang>

=={{header|F_Sharp|F#}}==

===~~Simple Backtracker~~===

===Backtracking===

<~~lang~~ fsharp>module SudokuBacktrack

<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

Line 4,023:

Line 4,180:

/// Outputs single line puzzle with 0 as empty squares

let asString = function

| Some values' -> values' |> Map.toSeq |> Seq.map (snd>>string) |> String.concat ""

| 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<_,_>) ->

| Some (values:Map<_,_>) ->

[for r in rows do [for c in cols do (values'[key r c] |> string) ] |> String.concat " " ] |> String.concat "\n"

[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~~

/// 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 = seq {for p in peers[s] do values[p] = d} |> Seq.exists ((=) true) |> not

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 ~~recursvely~~ and immutably from index

/// Backtrack recursively and immutably from index

let rec ~~backtrack s~~ (values:Map<~~string~~,~~int~~>) =

let rec backtracker (values:Map<_,_>) = function

match s with

| None -> Some values // solved!

| Some s' when values[s'] > 0 -> ~~backtrack~~ (next s') ~~values~~ // square not empty

| Some s when values[s] > 0 -> backtracker values (next s) // square not empty

| Some s' ->

| Some s ->

let rec tracker ~~(vx:Map<_,_>)~~ dx =

let rec tracker = function

match dx with

| [] -> None

| d::dx' ->

| d::dx ->

~~let vx' = vx |> Map.change s' (Option.map (fun _ -> d))~~

values

~~match~~ ~~backtrack~~ (~~next~~ ~~s')~~ ~~vx'~~ ~~with~~

|> Map.change s (Option.map (fun _ -> d))

| ~~None -~~> ~~tracker~~ vx ~~dx'~~

|> flip backtracker (next s)

|> function

| None -> tracker dx

| success -> success

[for d in 1..9 do if constraints values s d then d] |> tracker

[1..9]

|> List.filter (constraints values s')

|> tracker values

/// solve sudoku using simple backtracking

let solve grid = grid |> parseGrid >>= ~~backtrack~~ (Some "A1")

let solve grid = grid |> parseGrid >>= flip backtracker (Some "A1")</syntaxhighlight>

</lang>

'''Usage:'''

<~~lang~~ fsharp>open System

<syntaxhighlight lang="fsharp">open System

open SudokuBacktrack

Line 4,072:

Line 4,227:

printfn "Press any key to exit"

Console.ReadKey() |> ignore

0</~~lang~~>

0</syntaxhighlight>

{{Output}}<pre>

Puzzle:

Line 4,099:

Line 4,254:

</pre>

===~~The~~ ~~Function~~ ~~SLPsolve~~===

===Constraint Satisfaction (Norvig)===

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

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

// 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,129:

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

</syntaxhighlight>

</lang>

'''Usage:'''

Given sud1.csv:

Line 4,144:

Line 4,532:

</pre>

then

<~~lang~~ fsharp>

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>

</lang>

<pre>

Line 4,163:

Line 4,551:

=={{header|Forth}}==

<~~lang~~ forth>include lib/interprt.4th

<syntaxhighlight lang="forth">include lib/interprt.4th

include lib/istype.4th

include lib/argopen.4th

Line 4,526:

Line 4,914:

;

sudoku</~~lang~~>

sudoku</syntaxhighlight>

=={{header|Fortran}}==

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.

<~~lang~~ fortran>program sudoku

<syntaxhighlight lang="fortran">program sudoku

implicit none

Line 4,628:

Line 5,016:

end subroutine pretty_print

end program sudoku</~~lang~~>

end program sudoku</syntaxhighlight>

{{out}}<pre>

+-----+-----+-----+

Line 4,661:

Line 5,049:

=={{header|FreeBASIC}}==

<~~lang~~ freebasic>Dim Shared As Integer cuadricula(9, 9), cuadriculaResuelta(9, 9)

<syntaxhighlight lang="freebasic">Dim Shared As Integer cuadricula(9, 9), cuadriculaResuelta(9, 9)

Function isSafe(i As Integer, j As Integer, n As Integer) As Boolean

Line 4,747:

Line 5,135:

If (i Mod 3 = 0) Then Print !"\n---------+---------+---------" Else Print

Next i

Sleep</~~lang~~>

Sleep</syntaxhighlight>

<pre>

Line 4,769:

Line 5,157:

=={{header|FutureBasic}}==

First is a short version:

<~~lang~~ futurebasic>

include "ConsoleWindow"

include "NSLog.incl"

include "Util_Containers.incl"

begin globals

~~dim as~~ container gC

container gC

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;

for (i = 0; i < 9; i++)

{

short i;

if (i != c && sudoku[r][i] == sudoku[r][c]) return 0;

short rr, cc;

if (i != r && sudoku[i][c] == sudoku[r][c]) return 0;

rr = r/3 * 3 + i/3;

cc = ~~c/3~~ * 3 + i~~%3;~~

for (i = 0; i < 9; i++)

if ((rr != r || cc != c) && sudoku[rr][cc] == sudoku[r][c]) return 0;

}

return -1;

}

short solve_sudoku( short i )

{

short r, c;

if (i < 0) return 0;

else if (i >= 81) return -1;

r = i / 9;

c = i % 9;

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;

if (i != c && sudoku[r][i] == sudoku[r][c]) return 0;

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 0;

return -1;

}

CFMutableStringRef print_sudoku()

{

short i, j;

CFMutableStringRef mutStr;

mutStr = CFStringCreateMutable( kCFAllocatorDefault, 0 );

short solve_sudoku( short i )

{

for (i = 0; i < 9; i++)

{

short r, c;

for (j = 0; j < 9; j++)

{

if (i < 0) return 0;

else if (i >= 81) return -1;

CFStringAppendFormat( mutStr, NULL, (CFStringRef)@" %d", sudoku[i][j] );

}

r = i / 9;

CFStringAppendFormat( mutStr, NULL, (CFStringRef)@"\r" );

}

c = i % 9;

return( mutStr );

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,859:

Line 5,244:

toolbox fn print_sudoku() = CFMutableStringRef

~~dim as~~ short solution

short solution

~~dim as~~ CFMutableStringRef cfRef

CFMutableStringRef cfRef

gC = " "

Line 4,871:

Line 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

</lang>

HandleEvents

</syntaxhighlight>

Output:

Line 4,910:

Line 5,297:

More code in this one, but faster execution:

<pre>

include "ConsoleWindow"

include "Tlbx Timer.incl"

begin globals

_digits = 9

Line 4,921:

Line 5,305:

begin record Board

~~dim~~ as ~~boolean~~ f(_digits,_digits,_digits)

Boolean f(_digits,_digits,_digits)

~~dim~~ as char match(_digits,_digits)

char match(_digits,_digits)

~~dim~~ as pointer previousBoard // singly-linked list used to discover repetitions

pointer previousBoard // singly-linked list used to discover repetitions

dim &&

end record

~~dim~~ quiz ~~as board~~

Board quiz

CFTimeInterval t

dim as long t

dim as double sProgStartTime

end globals

// 'ordinary' timer used for playing

local fn Milliseconds as long // time in ms since prog start

'~'1

dim as UnsignedWide us

long if ( sProgStartTime == 0.0 )

Microseconds( @us )

sProgStartTime = 4294967296.0*us.hi + us.lo

end if

Microseconds( @us )

end fn = (4294967296.0*us.hi + us.lo - sProgStartTime)'*1e-3

local fn InitMilliseconds

'~'1

sProgStartTime = 0.0

fn Milliseconds

end fn

local mode

local fn CopyBoard( source as ^Board, dest as ^Board )

BlockMoveData( source, dest, sizeof( Board ) )

'~'1

dest.previousBoard = source // linked list

BlockMoveData( source, dest, sizeof( Board ) )

dest.previousBoard = source // linked list

end fn

local fn prepare( b as ^Board )

short i, j, n

'~'1

dim as short i, j, n

for i = 1 to _digits

for j = 1 to _digits

for n = 1 to _digits

b.match[i, j] = 0

for n = 1 to _digits

b.~~match~~[i, j] = 0

b.f[i, j, n] = _true

next n

b.f[i, j, n] = _true

next n

next j

next i

end fn

local fn printBoard( b as ^Board )

short i, j

'~'1

dim as short i, j

for i = 1 to _digits

for j = 1 to _digits

Print b.match[i, j];

for j = 1 to _digits

next j

Print b.match[i, j];

print

next j

next i

print

next i

end fn

local fn verifica( b as ^Board )

short i, j, n, first, x, y, ii

'~'1

Boolean check

dim as short i, j, n, first, x, y, ii

dim as boolean check

check = _true

for i = 1 to _digits

for j = 1 to _digits

if ( b.match[i, j] == 0 )

for j = 1 to _digits

check = _false

long if ( b.match[i, j] == 0 )

for n = 1 to _digits

check = _false

if ( b.f[i, j, n] != _false )

for n = 1 to _digits

check = _true

long if ( b.f[i, j, n] != _false )

end if

check = _true

next n

end if

if ( check == _false ) then exit fn

next n

end if

if ( check == _false ) then exit fn

next j

end if

next j

next i

check = _true

for j = 1 to _digits

check = _true

for j = 1 to _digits

for n = 1 to _digits

~~for~~ n = 1 to ~~_digits~~

first = 0

for i = 1 to _digits

first = 0

if ( b.match[i, j] == n )

for i = 1 to _digits

~~long~~ if ( ~~b.match[i, j]~~ == n )

if ( first == 0 )

~~long~~ if ( first =~~= 0~~ )

first = i

else

first = i

check = _false

xelse

exit fn

check = _false

end if

exit fn

end if

next i

end if

next i

next n

next j

for i = 1 to _digits

for n = 1 to _digits

~~for~~ n = 1 to ~~_digits~~

first = 0

for j = 1 to _digits

first = 0

if ( b.match[i, j] == n )

for j = 1 to _digits

~~long~~ if ( ~~b.match[i, j]~~ == n )

if ( first == 0 )

~~long~~ if ( first =~~= 0~~ )

first = j

else

first = j

check = _false

xelse

exit fn

check = _false

end if

exit fn

end if

next j

end if

next j

next n

next i

for x = 0 to ( _nSetH - 1 )

for x = 0 to ( ~~_nSetH~~ - 1 )

for y = 0 to ( _nSetV - 1 )

~~for~~ y = 0 to ( ~~_nSetV~~ - ~~1 )~~

first = 0

for ii = 0 to ( _digits - 1 )

first = 0

i = x * _setH + ii mod _setH + 1

for ii = 0 to ( _digits - 1 )

i = x * ~~_setH~~ + ii ~~mod~~ _setH + 1

j = y * _setV + ii / _setH + 1

j = y * ~~_setV~~ + ii / ~~_setH~~ + 1

if ( b.match[i, j] == n )

~~long~~ if ( ~~b.match[i, j]~~ == n )

if ( first == 0 )

~~long~~ if ( first =~~= 0~~ )

first = j

else

first = j

check = _false

xelse

exit fn

check = _false

end if

exit fn

end if

next ii

end if

next ii

next y

next x

end fn = check

local fn setCell( b as ^Board, x as short, y as short, n as short) as boolean

~~dim~~ as short i, j, rx, ry

short i, j, rx, ry

~~dim~~ as ~~boolean~~ check

Boolean check

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 )

~~dim~~ as short i, j, n, first, x, y, ii, ppi, ppj

short i, j, n, first, x, y, ii, ppi, ppj

~~dim~~ as ~~boolean~~ check

Boolean check

check = _true

for i = 1 to _digits

for j = 1 to _digits

~~long~~ if ( b.match[i, j] == 0 )

if ( b.match[i, j] == 0 )

first = 0

for n = 1 to _digits

~~long~~ if ( b.f[i, j, n] != _false )

if ( b.f[i, j, n] != _false )

~~long~~ if ( first == 0 )

if ( first == 0 )

first = n

else

xelse

first = -1

exit for

end if

next n

~~long~~ if ( first > 0 )

if ( first > 0 )

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

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

~~long~~ if ( b.f[i, j, n] != _false ) and ( b.match[i, j] == 0 )

if ( b.f[i, j, n] != _false ) and ( b.match[i, j] == 0 )

~~long~~ if ( first == 0 )

if ( first == 0 )

first = j

else

xelse

first = -1

exit for

end if

next j

~~long~~ if ( first > 0 )

if ( first > 0 )

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

~~long~~ if ( b.f[i, j, n] != _false ) and ( b.match[i, j] == 0 )

if ( b.f[i, j, n] != _false ) and ( b.match[i, j] == 0 )

~~long~~ if ( first == 0 )

if ( first == 0 )

first = i

else

xelse

first = -1

exit for

end if

next i

~~long~~ if ( first > 0 )

if ( first > 0 )

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

~~long~~ if ( b.f[i, j, n] != _false ) and ( b.match[i, j] == 0 )

if ( b.f[i, j, n] != _false ) and ( b.match[i, j] == 0 )

~~long~~ if ( first == 0 )

if ( first == 0 )

first = n

ppi = i

ppj = j

else

xelse

first = -1

exit for

end if

next ii

~~long~~ if ( first > 0 )

if ( first > 0 )

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 )

~~dim~~ as ~~boolean~~ check, daFinire

Boolean check, daFinire

~~dim~~ as long i, j, n

long i, j, n

~~dim~~ as ~~board~~ localBoard

Board localBoard

check = fn solve(b)

~~long~~ if ( check == _false )

if ( check == _false )

exit fn

end if

daFinire = _false

for i = 1 to _digits

for j = 1 to _digits

~~long~~ if ( b.match[i, j] == 0 )

if ( b.match[i, j] == 0 )

daFinire = _true

for n = 1 to _digits

~~long~~ if ( b.f[i, j, n] != _false )

if ( b.f[i, j, n] != _false )

fn CopyBoard( b, @localBoard )

check = fn setCell(@localBoard, i, j, n)

~~long~~ if ( check != _false )

if ( check != _false )

check = fn resolve( @localBoard )

~~long~~ if ( check == -1 )

if ( check == -1 )

fn CopyBoard( @localBoard, b )

exit fn

end if

next n

end if

next j

next i

~~long~~ if daFinire

if daFinire

else

xelse

check = -1

end if

end fn = check

fn InitMilliseconds

fn prepare( @quiz )

Line 5,283:

Line 5,642:

DATA 2,8,0,1,3,0,0,0,0

~~dim as~~ short i, j, d

short i, j, d

for i = 1 to _digits

for j = 1 to _digits

read d

fn setCell(@quiz, j, i, d)

next j

next i

Line 5,294:

Line 5,653:

fn printBoard( @quiz )

print : print "-------------------" : print

~~dim as boolean~~ check

Boolean check

t = fn ~~Milliseconds~~

t = fn CACurrentMediaTime

check = fn resolve(@quiz)

t = fn ~~Milliseconds~~ - t

t = (fn CACurrentMediaTime - t) * 1000

if ( check )

print "solution:"; str$( t~~/1000.0~~ ) + " ms"

print "solution:"; str$( t ) + " ms"

else

print "No solution found"

end if

fn printBoard( @quiz )

HandleEvents

</pre>

Line 5,340:

Line 5,701:

Input to function solve is an 81 character string.

This seems to be a conventional computer representation for Sudoku puzzles.

<~~lang~~ go>package main

<syntaxhighlight lang="go">package main

import "fmt"

Line 5,541:

Line 5,902:

}

c.r.l, c.l.r = &c.x, &c.x

}</~~lang~~>

}</syntaxhighlight>

<pre>

Line 5,574:

Line 5,935:

Imprime todas las soluciones posibles, sale con un error, pero funciona.

<~~lang~~ golfscript>

'Solution:'

;'2 8 4 3 7 5 1 6 9

Line 5,588:

Line 5,949:

~]{:@0?:^~!{@p}*10,@9/^9/=-@^9%>9%-@3/^9%3/>3%3/^27/={+}*-{@^<\+@1^+>+}/1}do

</syntaxhighlight>

</lang>

=={{header|Groovy}}==

Line 5,596:

Line 5,957:

I consider this a "brute force" solution of sorts, in that it is the same method I use when solving Sudokus manually.

<~~lang~~ groovy>final CELL_VALUES = ('1'..'9')

<syntaxhighlight lang="groovy">final CELL_VALUES = ('1'..'9')

class GridException extends Exception {

Line 5,663:

Line 6,024:

}

grid

}</~~lang~~>

}</syntaxhighlight>

'''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]]

<~~lang~~ groovy>def sudokus = [

<syntaxhighlight lang="groovy">def 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,730:

Line 6,091:

solution.each { println it }

println "\nELAPSED: ${elapsed} seconds"

}</~~lang~~>

}</syntaxhighlight>

{{out}} (last only):

Line 5,764:

Line 6,125:

=={{header|Java}}==

<~~lang~~ java>public class Sudoku

<syntaxhighlight lang="java">public class Sudoku

{

private int mBoard[][];

Line 5,882:

Line 6,243:

}

}</~~lang~~>

}</syntaxhighlight>

Line 5,921:

Line 6,282:

====ES6====

<~~lang~~ ~~JavaScript~~>//-------------------------------------------[ Dancing Links and Algorithm X ]--

<syntaxhighlight lang="javascript">//-------------------------------------------[ Dancing Links and Algorithm X ]--

/**

* The doubly-doubly circularly linked data object.

Line 6,194:

Line 6,555:

search(H, []);

};

</syntaxhighlight>

</lang>

<syntaxhighlight lang="javascript">[

<lang JavaScript>[

'819..5.....2...75..371.4.6.4..59.1..7..3.8..2..3.62..7.5.7.921..64...9.....2..438',

'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,221:

Line 6,582:

let s = new Array(Math.pow(n, 4)).fill('.').join('');

reduceGrid(s);

</syntaxhighlight>

</lang>

<pre>+-------+-------+-------+

Line 6,250:

Line 6,611:

| 7 8 2 | 6 9 3 | 5 4 1 |

+-------+-------+-------+

</pre>

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

## 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:

# 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>

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

<~~lang~~ julia>function check(i, j)

<syntaxhighlight lang="julia">function check(i, j)

id, im = div(i, 9), mod(i, 9)

jd, jm = div(j, 9), mod(j, 9)

Line 6,276:

Line 6,818:

for i in 1:81

if grid[i] == 0

t = Dict{Int64, ~~Void~~}()

t = Dict{Int64, Nothing}()

for j in 1:81

Line 6,319:

Line 6,861:

0, 5, 0, 6, 9, 0, 0, 1, 0]

solve_sudoku(display, grid)</~~lang~~>

solve_sudoku(display, grid)</syntaxhighlight>

<pre>

Line 6,337:

Line 6,879:

=={{header|Kotlin}}==

<~~lang~~ scala>// version 1.2.10

<syntaxhighlight lang="scala">// version 1.2.10

class Sudoku(rows: List<String>) {

Line 6,420:

Line 6,962:

)

Sudoku(rows).solve()

}</~~lang~~>

}</syntaxhighlight>

Line 6,455:

Line 6,997:

=={{header|Lua}}==

===without FFI, slow===

<~~lang~~ lua>--9x9 sudoku solver in lua

<syntaxhighlight lang="lua">--9x9 sudoku solver in lua

--based on a branch and bound solution

--fields are not tried in plain order

Line 6,637:

Line 7,179:

if x then

return printer(x)

end</~~lang~~>

end</syntaxhighlight>

Input:

<pre>

Line 6,669:

Line 7,211:

Time with luajit: 9.245s

===with FFI, fast===

<~~lang~~ lua>#!/usr/bin/env luajit

<syntaxhighlight lang="lua">#!/usr/bin/env luajit

ffi=require"ffi"

local printf=function(fmt, ...) io.write(string.format(fmt, ...)) end

Line 6,737:

Line 7,279:

... .8. .79

]])

end</~~lang~~>

end</syntaxhighlight>

<pre>> time ./sudoku_fast.lua

Line 6,756:

Line 7,298:

=={{header|Mathematica}}/{{header|Wolfram Language}}==

<~~lang~~ mathematica>solve[sudoku_] :=

<syntaxhighlight lang="mathematica">solve[sudoku_] :=

NestWhile[

Join @@ Table[

Line 6,765:

Line 7,307:

Extract[Partition[s, {3, 3}], Quotient[#, 3, -2]]]} & /@

Position[s, 0, {2}],

Length@Last@# &], {s, #}] &, {sudoku}, ! FreeQ[#, 0] &]</~~lang~~>

Length@Last@# &], {s, #}] &, {sudoku}, ! FreeQ[#, 0] &]</syntaxhighlight>

Example:

<lang>solve[{{9, 7, 0, 3, 0, 0, 0, 6, 0},

<syntaxhighlight lang="text">solve[{{9, 7, 0, 3, 0, 0, 0, 6, 0},

{0, 6, 0, 7, 5, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 8, 0, 5, 0},

Line 6,775:

Line 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}}]</~~lang~~>

{0, 4, 0, 0, 0, 7, 3, 0, 0}}]</syntaxhighlight>

<pre>{{{9, 7, 5, 3, 4, 2, 8, 6, 1}, {8, 6, 1, 7, 5, 9, 4, 3, 2}, {3, 2, 4,

Line 6,786:

Line 7,328:

For this to work, this code must be placed in a file named "sudokuSolver.m"

<~~lang~~ ~~MATLAB~~>function solution = sudokuSolver(sudokuGrid)

<syntaxhighlight lang="matlab">function solution = sudokuSolver(sudokuGrid)

%Define what each of the sub-boxes of the sudoku grid are by defining

Line 7,138:

Line 7,680:

%% End of program

end %end sudokuSolver</~~lang~~>

end %end sudokuSolver</syntaxhighlight>

[http://www.menneske.no/sudoku/eng/showpuzzle.html?number=6903541 Test Input]:

All empty cells must have a value of NaN.

<~~lang~~ ~~MATLAB~~>sudoku = [NaN NaN NaN NaN 8 3 9 NaN NaN

<syntaxhighlight lang="matlab">sudoku = [NaN NaN NaN NaN 8 3 9 NaN NaN

1 NaN NaN NaN NaN NaN NaN 3 NaN

NaN NaN 4 NaN NaN NaN NaN 7 NaN

Line 7,149:

Line 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]</~~lang~~>

NaN NaN NaN 2 5 NaN NaN NaN 6]</syntaxhighlight>

[http://www.menneske.no/sudoku/eng/solution.html?number=6903541 Output]:

<~~lang~~ ~~MATLAB~~>solution =

<syntaxhighlight lang="matlab">solution =

7 6 5 4 8 3 9 2 1

Line 7,161:

Line 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</~~lang~~>

4 7 3 2 5 8 1 9 6</syntaxhighlight>

=={{header|Nim}}==

<~~lang~~ nim>{.this: self.}

<syntaxhighlight lang="nim">{.this: self.}

type

Line 7,239:

Line 7,781:

var puzzle = Sudoku()

puzzle.init(rows)

puzzle.solve()</~~lang~~>

puzzle.solve()</syntaxhighlight>

Line 7,272:

Line 7,814:

=={{header|OCaml}}==

uses the library [http://ocamlgraph.lri.fr/index.en.html ocamlgraph]

<~~lang~~ ocaml>(* Ocamlgraph demo program: solving the Sudoku puzzle using graph coloring

<syntaxhighlight lang="ocaml">(* Ocamlgraph demo program: solving the Sudoku puzzle using graph coloring

Line 7,341:

Line 7,883:

module C = Coloring.Mark(G)

let () = C.coloring g 9; display ()</~~lang~~>

let () = C.coloring g 9; display ()</syntaxhighlight>

=={{header|Oz}}==

Using built-in constraint propagation and search.

<~~lang~~ oz>declare

<syntaxhighlight lang="oz">declare

%% a puzzle is a function that returns an initial board configuration

fun {Puzzle1}

Line 7,428:

Line 7,970:

end

in

{Inspect {Solve Puzzle1}.1}</~~lang~~>

{Inspect {Solve Puzzle1}.1}</syntaxhighlight>

=={{header|PARI/GP}}==

Build plugin for PARI's function interface from C code: sudoku.c

<~~lang~~ C>#include <pari/pari.h>

<syntaxhighlight lang="c">#include <pari/pari.h>

typedef int SUDOKU [9][9];

Line 7,503:

Line 8,045:

return gen_0; /* no solution */

}

</syntaxhighlight>

</lang>

Compile plugin: gcc -O2 -Wall -fPIC -shared sudoku.c -o libsudoku.so -lpari

Install plugin from home directory and play:

<~~lang~~ parigp>install("plug_sudoku", "G", "sudoku", "~/libsudoku.so")</~~lang~~>

<syntaxhighlight lang="parigp">install("plug_sudoku", "G", "sudoku", "~/libsudoku.so")</syntaxhighlight>

Output:<pre> gp > S=[5,3,0,0,7,0,0,0,0;6,0,0,1,9,5,0,0,0;0,9,8,0,0,0,0,6,0;8,0,0,0,6,0,0,0,3;4,0,0,8,0,3,0,0,1;7,0,0,0,2,0,0,0,6;0,6,0,0,0,0,2,8,0;0,0,0,4,1,9,0,0,5;0,0,0,0,8,0,0,7,9]

Line 7,535:

Line 8,077:

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.

<~~lang~~ pascal>Program soduko;

<syntaxhighlight lang="pascal">Program soduko;

{$IFDEF FPC}

{$CODEALIGN proc=16,loop=8}

Line 7,791:

Line 8,333:

Outfield(solF);

writeln(86400*1000*(T1-T0)/k:10:3,' ms Test calls :',callCnt/k:8:0);

end.</~~lang~~>

end.</syntaxhighlight>

<pre>

Line 7,827:

Line 8,369:

=={{header|Perl}}==

<~~lang~~ ~~Perl~~>#!/usr/bin/perl

<syntaxhighlight lang="perl">#!/usr/bin/perl

use integer;

use strict;

Line 7,866:

Line 8,408:

}

solve();</~~lang~~>

solve();</syntaxhighlight>

<pre>

Line 7,884:

Line 8,426:

=={{header|Phix}}==

Simple brute force solution. Generally quite good but will struggle on some puzzles (eg see "the beast" below)

<lang Phix>sequence board = split("""

with javascript_semantics

.......39

sequence board = split("""

.....1..5

..3.5.8..

.......39

..8.9...6

.....1..5

.7...2...

..3.5.8..

1..4.....

..8.9...6

..9.8..5.

.7...2...

.2....6..

1..4.....

4..7....~~.""",'\n')~~

..9.8..5.

.2....6..

4..7.....""",'\n')

function valid_move(integer y, integer x, integer ch)

for i=1 to 9 do

function valid_move(integer y, x, ch)

if ch=board[i][x] then return 0 end if

for i=1 to 9 do

if ch=board[y][i] then return 0 end if

if ch=board[i][x] then return false end if

end for

if ch=board[y][i] then return false end if

y -= mod(y-1,3)

end for

x -= mod(x-1,3)

y -= mod(y-1,3)

for ys=y to y+2 do

x -= mod(x-1,3)

for xs=x to x+2 do

for ys=y to y+2 do

if ch=board[ys][xs] then return 0 end if

for xs=x to x+2 do

end for

if ch=board[ys][xs] then return false end if

end for

end for

return 1

end for

end function

return true

end function

sequence solution = {}

sequence solution = {}

procedure brute_solve()

for y=1 to 9 do

procedure brute_solve()

for x=1 to 9 do

for y=1 to 9 do

if board[y][x]<='0' then

for x=1 to 9 do

for ch='1' to '9' do

if board[y][x]<='0' then

if valid_move(y,x,ch) then

for ch='1' to '9' do

board[y][x] = ch

if valid_move(y,x,ch) then

brute_solve()

board[y][x] = ch

board[y][x] = ' '

if ~~length(solution)~~ ~~then~~ ~~return~~ ~~end~~ if

brute_solve()

board[y][x] = ' '

end if

if length(solution) then return end if

end for

end if

return

end for

end if

return

end for

end if

end for

end for

solution = board -- (already solved case)

end for

end procedure

solution = deep_copy(board) -- (already solved case)

end procedure

atom t0 = time()

brute_solve()

atom t0 = time()

printf(1,"%s\n(solved in %3.2fs)\n",{join(solution,"\n"),time()-t0})</lang>

brute_solve()

printf(1,"%s\n(solved in %3.2fs)\n",{join(solution,"\n"),time()-t0})

<pre>

Line 7,951:

Line 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).

<lang Phix>-- Working directly on 81-character strings ultimately proves easier: Originally I

with javascript_semantics

-- just wanted to simplify the final display, but later I realised that a 9x9 grid

-- Working directly on 81-character strings ultimately proves easier: Originally I

-- encourages laborious indexing/looping everwhere whereas using a flat 81-element

-- just wanted to simplify the final display, but later I realised that a 9x9 grid

-- approach encourages precomputation of index sets, and once you commit to that,

-- encourages laborious indexing/looping everwhere whereas using a flat 81-element

-- the rest of the code starts to get a whole lot cleaner. Below we create 27+18

-- approach encourages precomputation of index sets, and once you commit to that,

-- sets and 5 tables of lookup indexes to locate them quickly.

-- 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.

sequence nines = {}, -- will be 27 in total

cols = repeat(0,9*9), -- remainder(i-1,9)+1

sequence nines = {}, -- will be 27 in total

rows = repeat(0,9*9), -- floor((i-1)/9)+10

cols = repeat(0,9*9), -- remainder(i-1,9)+1

squares = repeat(0,9*9),

rows = repeat(0,9*9), -- floor((i-1)/9)+10

sixes = {}, -- will be 18 in total

squares = repeat(0,9*9),

dotcol = repeat(0,9*9), -- same col, diff square

sixes = {}, -- will be 18 in total

dotrow = repeat(0,9*9) -- same row, diff square

dotcol = repeat(0,9*9), -- same col, diff square

dotrow = repeat(0,9*9) -- same row, diff square

procedure set_nines()

sequence nine, six

procedure set_nines()

integer idx, ndx

sequence nine, six

for x=0 to 8 do -- columns

integer idx, ndx

nine = {}

for x=0 to 8 do -- columns

ndx = length(nines)+1

nine = {}

for y=1 to 81 by 9 do

ndx = length(nines)+1

idx = y+x

for y=1 to 81 by 9 do

nine = append(nine,idx)

idx = y+x

cols[idx] = ndx

nine = append(nine,idx)

end for

cols[idx] = ndx

nines = append(nines,nine)

end for

end for

nines = append(nines,nine)

for y=1 to 81 by 9 do -- rows

end for

nine = {}

for y=1 to 81 by 9 do -- rows

ndx = length(nines)+1

nine = {}

for x=0 to 8 do

ndx = length(nines)+1

idx = y+x

for x=0 to 8 do

nine = append(nine,idx)

idx = y+x

rows[idx] = ndx

nine = append(nine,idx)

end for

rows[idx] = ndx

nines = append(nines,nine)

end for

end for

nines = append(nines,nine)

if length(nines)!=18 then ?9/0 end if

end for

for y=0 to 8 by 3 do -- small squares [19..27]

if length(nines)!=18 then ?9/0 end if

for x=0 to 8 by 3 do

for y=0 to 8 by 3 do -- small squares [19..27]

nine = {}

for x=0 to 8 by 3 do

ndx = length(nines)+1

nine = {}

for sy=y*9 to y*9+18 by 9 do

ndx = length(nines)+1

for sx=x to x+2 do

for sy=y*9 to y*9+18 by 9 do

idx = sy+sx+1

for sx=x to x+2 do

nine = append(nine,idx)

idx = sy+sx+1

squares[idx] = ndx

nine = append(nine,idx)

end for

squares[idx] = ndx

end for

end for

nines = append(nines,nine)

end for

end for

nines = append(nines,nine)

end for

end for

if length(nines)!=27 then ?9/0 end if

end for

for i=1 to 9*9 do

if length(nines)!=27 then ?9/0 end if

six = {}

for i=1 to 9*9 do

nine = nines[cols[i]] -- dotcol

six = {}

for j=1 to length(nine) do

nine = nines[cols[i]] -- dotcol

if squares[i]!=squares[nine[j]] then

for j=1 to length(nine) do

six = append(six,nine[j])

if squares[i]!=squares[nine[j]] then

end if

six = append(six,nine[j])

end for

end if

ndx = find(six,sixes)

end for

if ndx=0 then

ndx = find(six,sixes)

sixes = append(sixes,six)

if ndx=0 then

ndx = length(sixes)

sixes = append(sixes,six)

end if

ndx = length(sixes)

dotcol[i] = ndx

end if

six = {}

dotcol[i] = ndx

nine = nines[rows[i]] -- dotrow

six = {}

for j=1 to length(nine) do

nine = nines[rows[i]] -- dotrow

if squares[i]!=squares[nine[j]] then

for j=1 to length(nine) do

six = append(six,nine[j])

if squares[i]!=squares[nine[j]] then

end if

six = append(six,nine[j])

end for

end if

ndx = find(six,sixes)

end for

if ndx=0 then

ndx = find(six,sixes)

sixes = append(sixes,six)

if ndx=0 then

ndx = length(sixes)

sixes = append(sixes,six)

end if

ndx = length(sixes)

dotrow[i] = ndx

end if

end for

dotrow[i] = ndx

end procedure

end for

set_nines()

end procedure

set_nines()

integer improved = 0

integer improved = 0

function eliminate_in(sequence valid, sequence set, integer ch)

for i=1 to length(set) do

function eliminate_in(sequence valid, set, integer ch)

integer idx = set[i]

for i=1 to length(set) do

if string(valid[idx]) then

integer idx = set[i]

integer k = find(ch,valid[idx])

if string(valid[idx]) then

if k!=0 then

integer k = find(ch,valid[idx])

valid[idx][k..k] = ""

if k!=0 then

improved = 1

valid[idx][k..k] = ""

end if

improved = 1

end if

end if

end for

end if

return valid

end for

end function

return valid

end function

function test_comb(sequence chosen, sequence pool, sequence valid)

--

function test_comb(sequence chosen, pool, valid)

-- (see deep_logic()/set elimination)

--

-- chosen is a sequence of length 2..4 of integers 1..9: ordered elements of pool.

-- (see deep_logic()/set elimination)

-- pool is a set of elements of the sequence valid, each of which is a sequence.

-- chosen is a sequence of length 2..4 of integers 1..9: ordered elements of pool.

-- (note that elements of valid in pool not in chosen are not necessarily sequences)

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

sequence contains = repeat(0,9)

--

integer ccount = 0, ch

sequence contains = repeat(0,9)

object set

integer ccount = 0, ch

object set

for i=1 to length(chosen) do

set = valid[pool[chosen[i]]]

for i=1 to length(chosen) do

for j=1 to length(set) do

set = valid[pool[chosen[i]]]

ch = set[j]-'0'

for j=1 to length(set) do

if contains[ch]=0 then

ch = set[j]-'0'

contains[ch] = 1

if contains[ch]=0 then

ccount += 1

contains[ch] = 1

end if

ccount += 1

end for

end if

end for

end for

if ccount=length(chosen) then

end for

for i=1 to length(pool) do

if ccount=length(chosen) then

if find(i,chosen)=0 then

valid = deep_copy(valid)

set = valid[pool[i]]

for i=1 to length(pool) do

if sequence(set) then

if find(i,chosen)=0 then

-- (reverse order so deletions don't foul indexes)

set = valid[pool[i]]

for j=length(set) to 1 by -1 do

if sequence(set) then

ch = set[j]-'0'

-- (reverse order so deletions don't foul indexes)

if contains[ch] then

for j=length(set) to 1 by -1 do

valid[pool[i]][j..j] = ""

ch = set[j]-'0'

improved = 1

if contains[ch] then

end if

valid[pool[i]][j..j] = ""

end for

improved = 1

end if

end if

end if

end for

end for

end if

end if

end if

return valid

end for

end function

end if

return valid

-- from [[Combinations#Phix|Combinations]]

end function

-- from http://rosettacode.org/wiki/Combinations#Phix

function comb(sequence pool, valid, integer needed, done=0, sequence chosen={})

-- from [[Combinations#Phix|Combinations]]

-- (used by deep_logic()/set elimination)

-- from http://rosettacode.org/wiki/Combinations#Phix

if needed=0 then -- got a full set

function comb(sequence pool, valid, integer needed, done=0, sequence chosen={})

return test_comb(chosen,pool,valid)

-- (used by deep_logic()/set elimination)

end if

if needed=0 then -- got a full set

if done+needed>length(pool) then return valid end if -- cannot fulfil

return test_comb(chosen,pool,valid)

-- get all combinations with and without the next item:

end if

done += 1

if done+needed>length(pool) then return valid end if -- cannot fulfil

if sequence(valid[pool[done]]) then

-- get all combinations with and without the next item:

valid = comb(pool,valid,needed-1,done,append(chosen,done))

done += 1

end if

if sequence(valid[pool[done]]) then

return comb(pool,valid,needed,done,chosen)

valid = comb(pool,valid,needed-1,done,append(deep_copy(chosen),done))

end function

end if

return comb(pool,valid,needed,done,chosen)

function deep_logic(string board, sequence valid)

end function

--

-- Create a grid of valid moves. Note this does not modify board, but instead creates

function deep_logic(string board, sequence valid)

-- 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:

-- 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.

-- 1) row/col elimination

-- Apply standard eliminations of known cells, then try some more advanced tactics:

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

-- 1) row/col elimination

-- small squares. Example (this one with significant practical benefit):

-- If in any of the 9 small squares a number can only occur in one row or column,

-- 000|000|036

-- then that number cannot occur in that row or column in two other corresponding

-- 840|000|000

-- small squares. Example (this one with significant practical benefit):

-- 000|000|020

-- ~~---+---+---~~

-- 000|000|036

-- ~~000~~|~~203~~|000

-- 840|000|000

-- ~~010~~|000|~~700~~

-- 000|000|020

-- ~~000|600|400~~

-- ---+---+---

-- ~~---+---+---~~

-- 000|203|000

-- ~~000~~|~~410~~|~~050~~

-- 010|000|700

-- ~~003|~~000|~~200~~

-- 000|600|400

-- ~~600|000|000 <~~-- 3

-- ---+---+---

-- ~~^-- 3~~

-- 000|410|050

-- 003|000|200

-- Naively, the br can contain a 3 in the four corners, but looking at mid-right and

-- 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.~~

-- ^-- 3

-- ~~Without this~~, ~~brute~~ ~~force~~ on ~~the~~ ~~above~~ ~~takes~~ ~~~8s~~, but ~~with~~ it ~~~0s~~

-- Naively, the br can contain a 3 in the four corners, but looking at mid-right and

-- 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.

-- 2) set elimination

-- Without this, brute force on the above takes ~8s, but with it ~0s

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

-- 2) set elimination

-- 75.|.9.|.46

-- If in any 9-set there is a set of n blank squares that can only contain n digits,

-- 961|...|352

-- then no other squares can contain those digits. Example (with some benefit):

-- 4..|...|79.

-- ~~---+---+---~~

-- 75.|.9.|.46

-- 2..|6.1|~~..7~~

-- 961|...|352

-- .8.|...|.2.

-- 4..|...|79.

-- ~~1..|328|.65~~

-- ---+---+---

-- ~~---+---+---~~

-- 2..|6.1|..7

-- ...|...|..~~. <-- [7,8] is {1,3,8}, [7,9] is {1,3,8}~~

-- .8.|...|.2.

-- ~~3.9|.~~..|2.~~4 <-- [8,8] is {1,8}~~

-- 1..|328|.65

-- ~~84.|.3.|.79~~

-- ---+---+---

-- ~~The~~ ~~three~~ ~~cells~~ ~~above~~ ~~the~~ br ~~479~~ ~~can~~ ~~only~~ ~~contain~~ {1,3,8}, so ~~the .. of the .2.~~

-- ...|...|... <-- [7,8] is {1,3,8}, [7,9] is {1,3,8}

-- in ~~column~~ 7 of ~~that~~ ~~square~~ ~~are~~ ~~{5,6}~~ ~~(not~~ 1) ~~and~~ ~~hence~~ [9,4] ~~must be a~~ 1.

-- 3.9|...|2.4 <-- [8,8] is {1,8}

-- 84.|.3.|.79

-- (Relies on plain_logic to spot that "must be a 1", and serves as a clear example

-- of ~~why~~ ~~this~~ ~~routine~~ ~~should~~ ~~not~~ ~~bother~~ to ~~attempt~~ ~~updating~~ the ~~board~~ ~~itself~~ - as

-- The three cells above the br 479 can only contain {1,3,8}, so the .. of the .2.

-- it ~~spends~~ ~~almost~~ ~~all~~ of ~~its~~ ~~time~~ ~~looking~~ in a ~~completely~~ ~~different~~ ~~place~~.)

-- in column 7 of that square are {5,6} (not 1) and hence [9,4] must be a 1.

-- (~~One~~ ~~could~~ ~~argue~~ that ~~[7,7]~~ ~~and~~ [9,7] ~~are~~ ~~the~~ ~~only~~ ~~places~~ ~~that~~ ~~can~~ ~~hold {5,6} and~~

-- (Relies on plain_logic to spot that "must be a 1", and serves as a clear example

-- ~~therefore~~ we should ~~eliminate~~ ~~all~~ ~~non-{5,6}~~ ~~from~~ ~~those~~ ~~squares,~~ as an ~~alternative~~

-- of why this routine should not bother to attempt updating the board itself - as

-- it spends almost all of its time looking in a completely different place.)

-- 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.)~~

-- (One could argue that [7,7] and [9,7] are the only places that can hold {5,6} and

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

-- 3) x-wings

-- said complementary logic covers, that the above does not, cmiiw.)

-- If a pair of rows or columns can only contain a given number in two matching places,

--

-- then once filled they will occupy opposite diagonal corners, hence that said number

-- 3) x-wings

-- cannot occur elsewhere in those two columns/rows. Example (with a benefit):

-- ~~.43|98.|25.~~ ~~<--~~ 6 in ~~[1,{6~~,~~9}]~~

-- If a pair of rows or columns can only contain a given number in two matching places,

-- then once filled they will occupy opposite diagonal corners, hence that said number

-- 6..|425|...

-- cannot occur elsewhere in those two columns/rows. Example (with a benefit):

-- 2..|..1|.94

-- --~~-+---+---~~

-- .43|98.|25. <-- 6 in [1,{6,9}]

-- 9..|..4|.~~7. <-- hence 6 not in [4,9]~~

-- 6..|425|...

-- 3..|6.8|...

-- 2..|..1|.94

-- ~~41.|2.9|..3~~

-- ---+---+---

-- --~~-+---+---~~

-- 9..|..4|.7. <-- hence 6 not in [4,9]

-- 82.|5..|... ~~<-- hence 6 not in [7,6],[7,9]~~

-- 3..|6.8|...

-- ...|.4.|..~~5 <-- hence 6 not in [8,6]~~

-- 41.|2.9|..3

-- ~~534|89.|71. <~~-- ~~6 in [9,{6,9}]~~

-- ---+---+---

-- A 6 ~~must~~ be in ~~[1,6]~~ or ~~[1,9]~~ ~~and~~ ~~[9,6]~~ or ~~[9,9],~~ ~~hence~~ ~~[7,9]~~ is ~~not~~ 6 ~~and~~ ~~must~~ be 9.

-- 82.|5..|... <-- hence 6 not in [7,6],[7,9]

-- ...|.4.|..5 <-- hence 6 not in [8,6]

-- (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

-- 534|89.|71. <-- 6 in [9,{6,9}]

-- ~~obviously~~ ~~trying~~ ~~either 6~~ in ~~row~~ 1 or 9 ~~immediately~~ ~~pinpoints~~ ~~that~~ 9 ~~anyway~~.

-- A 6 must be in [1,6] or [1,9] and [9,6] or [9,9], hence [7,9] is not 6 and must be 9.

-- (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

-- 4) swordfish (not attempted)

-- obviously trying either 6 in row 1 or 9 immediately pinpoints that 9 anyway.

-- 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:

-- 4) swordfish (not attempted)

-- 8-1|-5-|-3-

-- There is an extension to x-wings known as swordfish: three (or more) pairs form

-- 953|-68|---

-- a staggered pair (or more) of rectangles that exhibit similar properties, eg:

-- -4-|-*3|5*8

-- ---~~+---+-~~--

-- 8-1|-5-|-3-

-- ~~6--~~|9-2|---

-- 953|-68|---

-- -8-|-3-|~~-4-~~

-- -4-|-*3|5*8

-- 3*-|5-1|-*7 <-- ~~hence [6,3] is not 9, must be 4~~

-- ---+---+---

-- ---~~+---+~~---

-- 6--|9-2|---

-- ~~5*2~~|-*-|-8-

-- -8-|-3-|-4-

-- --8|37-|--9

-- 3*-|5-1|-*7 <-- hence [6,3] is not 9, must be 4

-- -3-~~|82~~-|1--

-- ---+---+---

-- ^---^-~~--^-- 3 pairs of 9s (marked with *) on 3 rows (only)~~

-- 5*2|-*-|-8-

-- --8|37-|--9

-- It is not a swordfish if the 3 pairs are on >3 rows, I trust that is obvious.

-- -3-|82-|1--

-- Logically you can extend this to N pairs on N rows, however I cannot imagine a

-- ^---^---^-- 3 pairs of 9s (marked with *) on 3 rows (only)

-- case where this is not immediately solved by a single trial-step being invalid.

-- ~~(eg~~ ~~above~~ if ~~you~~ ~~try~~ ~~[3,5]:=9~~ it is ~~quickly~~ ~~proved~~ to be ~~invalid~~, ~~and~~ ~~the~~ ~~same~~

-- It is not a swordfish if the 3 pairs are on >3 rows, I trust that is obvious.

-- Logically you can extend this to N pairs on N rows, however I cannot imagine a

-- goes for [6,8]:=9 and [7,2]:=9, since they are all entirely inter-dependent.)

-- ~~Obviously~~ where I ~~have~~ ~~said~~ ~~rows,~~ ~~the~~ ~~same~~ ~~concept~~ ~~can~~ ~~be applied~~ to ~~columns~~.

-- case where this is not immediately solved by a single trial-step being invalid.

-- (eg above if you try [3,5]:=9 it is quickly proved to be invalid, and the same

-- Likewise there are "Alternate Pairs" and "Hook or X-Y wing" strategies, which

-- goes for [6,8]:=9 and [7,2]:=9, since they are all entirely inter-dependent.)

-- 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,~~

-- Obviously where I have said rows, the same concept can be applied to columns.

-- Likewise there are "Alternate Pairs" and "Hook or X-Y wing" strategies, which

-- it selects shortest - I've noted the possible improvement below.]

-- 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,

integer col, row

-- it selects shortest - I've noted the possible improvement below.]

sequence c, r

--

sequence nine, prevsets, set

integer k -- (scratch)

object vj

if length(valid)=0 then

integer ch, k, idx, sx, sy, count

-- initialise/start again from scratch

valid = repeat("123456789",9*9)

if length(valid)=0 then

end if

-- initialise/start again from scratch

--

valid = repeat("123456789",9*9)

-- First perform standard eliminations of any known cells:

end if

-- (repeated every time so plain_logic() does not have to worry about it)

--

--

-- First perform standard eliminations of any known cells:

for i=1 to 9*9 do

-- (repeated every time so plain_logic() does not have to worry about it)

integer ch = board[i]

--

if ch>'0'

for i=1 to 9*9 do

and string(valid[i]) then

ch = board[i]

valid[i] = ch

if ch>'0'

valid = eliminate_in(valid,nines[cols[i]],ch)

and string(valid[i]) then

valid = eliminate_in(valid,nines[rows[i]],ch)

valid[i] = ch

valid = eliminate_in(valid,nines[squares[i]],ch)

valid = eliminate_in(valid,nines[cols[i]],ch)

end if

valid = eliminate_in(valid,nines[rows[i]],ch)

end for

valid = eliminate_in(valid,nines[squares[i]],ch)

--

end if

-- 1) row/col elimination

end for

--

--

for s=19 to 27 do

-- 1) row/col elimination

sequence c = repeat(0,9), -- 0 = none seen, 1..9 this col only, -1: >1 col

--

r = repeat(0,9), -- "" row row

for s=19 to 27 do

nine = nines[s]

c = repeat(0,9) -- 0 = none seen, 1..9 this col only, -1: >1 col

integer row, col, ch

r = repeat(0,9) -- "" row row

for n=1 to 9 do

nine = nines[s]

k = nine[n]

for n=1 to 9 do

object vk = valid[k]

k = nine[n]

if string(vk) then

vj = valid[k]

for i=1 to length(vk) do

if string(vj) then

ch = vk[i]-'0'

for i=1 to length(vj) do

col = dotcol[k]

ch = vj[i]-'0'

row = dotrow[k]

col = dotcol[k]

c[ch] = iff(find(c[ch],{0,col})!=0?col:-1)

row = dotrow[k]

r[ch] = iff(find(r[ch],{0,row})!=0?row:-1)

c[ch] = iff(find(c[ch],{0,col})!=0?col:-1)

end for

r[ch] = iff(find(r[ch],{0,row})!=0?row:-1)

end ~~for~~

end if

end for

end if

for i=1 to 9 do

end for

ch = i+'0'

for i=1 to 9 do

col = c[i]

ch = i+'0'

if col>0 then

col = c[i]

valid = eliminate_in(valid,sixes[col],ch)

if col>0 then

end if

valid = eliminate_in(valid,sixes[col],ch)

row = r[i]

end if

if row>0 then

row = r[i]

valid = eliminate_in(valid,sixes[row],ch)

if row>0 then

end if

valid = eliminate_in(valid,sixes[row],ch)

end for

end if

end for

end for

--

end for

--

-- 2) set elimination

-- ~~2) set elimination~~

--

for i=1 to length(nines) do

--

--

for i=1 to length(nines) do

-- Practical note: Meticulously counting empties to eliminate larger set sizes

--

-- would at best reduce 6642 tests to 972, not deemed worth it.

-- Practical note: Meticulously counting empties to eliminate larger set sizes

--

-- would at best reduce 6642 tests to 972, not deemed worth it.

for set_size=2 to 4 do

--

--if floor(count_empties(nines[i])/2)>=set_size then -- (untested)

for set_size=2 to 4 do

valid = comb(nines[i],valid,set_size)

--if floor(count_empties(nines[i])/2)>=set_size then -- (untested)

--end if

valid = comb(nines[i],valid,set_size)

end for

--end if

end for

end for

--

end for

--

-- 3) x-wings

-- ~~3) x-wings~~

--

for ch='1' to '9' do

--

sequence prevsets = repeat(0,9), set

for ch='1' to '9' do

integer count, idx

prevsets = repeat(0,9)

for x=1 to 9 do

for x=1 to 9 do

count = 0

count = 0

set = repeat(0,9)

set = repeat(0,9)

for y=0 to 8 do

for y=0 to 8 do

idx = y*9+x

idx = y*9+x

if sequence(valid[idx]) and find(ch,valid[idx]) then

if sequence(valid[idx]) and find(ch,valid[idx]) then

set[y+1] = 1

set[y+1] = 1

count += 1

count += 1

end if

end if

end for

end for

if count=2 then

if count=2 then

k = find(set,prevsets)

k = find(set,prevsets)

if k!=0 then

if k!=0 then

for y=0 to 8 do

for y=0 to 8 do

if set[y+1]=1 then

if set[y+1]=1 then

for sx=1 to 9 do

for sx=1 to 9 do

if sx!=k and sx!=x then

if sx!=k and sx!=x then

valid = eliminate_in(valid,{y*9+sx},ch)

valid = eliminate_in(valid,{y*9+sx},ch)

end if

end if

end for

end for

end if

end if

end for

end for

else

else

prevsets[x] = set

prevsets[x] = set

end if

end if

end if

end for

end for

prevsets = repeat(0,9)

prevsets = repeat(0,9)

for y=0 to 8 do

for y=0 to 8 do

count = 0

count = 0

set = repeat(0,9)

set = repeat(0,9)

for x=1 to 9 do

for x=1 to 9 do

idx = y*9+x

idx = y*9+x

if sequence(valid[idx]) and find(ch,valid[idx]) then

if sequence(valid[idx]) and find(ch,valid[idx]) then

set[x] = 1

set[x] = 1

count += 1

count += 1

end if

end if

end for

end for

if count=2 then

if count=2 then

k = find(set,prevsets)

k = find(set,prevsets)

if k!=0 then

if k!=0 then

for x=1 to 9 do

for x=1 to 9 do

if set[x]=1 then

if set[x]=1 then

for sy=0 to 8 do

for sy=0 to 8 do

if sy+1!=k and sy!=y then

if sy+1!=k and sy!=y then

valid = eliminate_in(valid,{sy*9+x},ch)

valid = eliminate_in(valid,{sy*9+x},ch)

end if

end if

end for

end for

end if

end if

end for

end for

else

else

prevsets[y+1] = set

prevsets[y+1] = set

end if

end if

end if

end for

end for

end for

end for

return valid

return valid

end function

end function

function permitted_in(string board, sequence sets, valid, integer ch)

function permitted_in(string board, sequence sets, sequence valid, integer ch)

for i=1 to 9 do

sequence set

sequence set = nines[sets[i]]

integer pos, idx, bch

integer pos = 0

for i=1 to 9 do

for j=1 to 9 do

set = nines[sets[i]]

integer idx = set[j],

pos = 0

bch = board[idx]

for j=1 to 9 do

if bch>'0' then

idx = set[j]

if bch=ch then pos = -1 exit end if

bch = board[idx]

elsif find(ch,valid[idx]) then

if bch>'0' then

if pos!=0 then pos = -1 exit end if

if bch=ch then pos = -1 exit end if

pos = idx

elsif find(ch,valid[idx]) then

~~if pos!~~=0 ~~then~~ ~~pos~~ = ~~-1 exit end~~ if

end if

end for

pos = idx

if pos>0 then

end if

board[pos] = ch

end for

improved = 1

if pos>0 then

end if

board[pos] = ch

end for

improved = 1

return board

end if

end function

end for

return board

enum INVALID = -1, INCOMPLETE = 0, SOLVED = 1, MULTIPLE = 2, BRUTE = 3

end function

function plain_logic(string board)

enum INVALID = -1, INCOMPLETE = 0, SOLVED = 1, MULTIPLE = 2, BRUTE = 3

--

-- Responsible for:

function plain_logic(string board)

-- 1) cells with only one option

--

-- 2) numbers with only one home

-- Responsible for:

--

-- 1) cells with only one option

integer solved

-- 2) numbers with only one home

sequence valid = {}

--

while true do

integer solved

solved = SOLVED

sequence valid = {}

improved = 0

object vi

valid = deep_logic(board,valid)

while 1 do

-- 1) cells with only one option:

solved = SOLVED

for i=1 to length(valid) do

improved = 0

object vi = valid[i]

valid = deep_logic(board,valid)

if string(vi) then

if length(vi)=0 then return {board,{},INVALID} end if

-- 1) cells with only one option:

if length(vi)=1 then

for i=1 to length(valid) do

board[i] = vi[1]

vi = valid[i]

improved = 1

if string(vi) then

if ~~length(vi)~~=0 ~~then~~ ~~return~~ ~~{board,{},INVALID} end~~ if

end if

if length(vi)=1 then

if board[i]<='0' then

board[i] = vi[1]

solved = INCOMPLETE

improved = 1

end if

end if

end for

end if

if solved=SOLVED then return {board,{},SOLVED} end if

if board[i]<='0' then

solved = INCOMPLETE

-- 2) numbers with only one home

end if

for ch='1' to '9' do

end for

board = permitted_in(board,cols,valid,ch)

if solved=SOLVED then return {board,{},SOLVED} end if

board = permitted_in(board,rows,valid,ch)

board = permitted_in(board,squares,valid,ch)

-- 2) numbers with only one home

end for

for ch='1' to '9' do

if not improved then exit end if

board = permitted_in(board,cols,valid,ch)

end while

board = permitted_in(board,rows,valid,ch)

return {board,valid,solved}

board = permitted_in(board,squares,valid,ch)

end function

end for

if not improved then exit end if

function validate(string board)

end while

-- (sum9 should be sufficient - if you want, get rid of nine/nines)

return {board,valid,solved}

integer ch, sum9

end function

sequence nine, nines = tagset(9)

function validate(string board)

for x=0 to 8 do -- columns

-- (sum9 should be sufficient - if you want, get rid of nine/nines)

sum9 = 0

integer ch, sum9

nine = repeat(0,9)

sequence nine, nines = tagset(9)

for y=1 to 81 by 9 do

ch = board[y+x]-'0'

for x=0 to 8 do -- columns

if ch<1 or ch>9 then return false end if

sum9 = 0

sum9 += ch

nine = repeat(0,9)

nine[ch] = ch

for y=1 to 81 by 9 do

end for

ch = board[y+x]-'0'

if sum9!=45 then return false end if

if ch<1 or ch>9 then return 0 end if

if nine!=nines then return false end if

sum9 += ch

end for

nine[ch] = ch

for y=1 to 81 by 9 do -- rows

end for

sum9 = 0

if sum9!=45 then return 0 end if

nine = repeat(0,9)

if nine!=nines then return 0 end if

for x=0 to 8 do

end for

ch = board[y+x]-'0'

for y=1 to 81 by 9 do -- rows

sum9 += ch

sum9 = 0

nine[ch] = ch

nine = repeat(0,9)

end for

for x=0 to 8 do

if sum9!=45 then return false end if

ch = board[y+x]-'0'

if nine!=nines then return false end if

sum9 += ch

end for

nine[ch] = ch

for y=0 to 8 by 3 do -- small squares

end for

for x=0 to 8 by 3 do

if sum9!=45 then return 0 end if

sum9 = 0

if nine!=nines then return 0 end if

nine = repeat(0,9)

end for

for sy=y*9 to y*9+18 by 9 do

for y=0 to 8 by 3 do -- small squares

for sx=x to x+2 do

for x=0 to 8 by 3 do

ch = board[sy+sx+1]-'0'

sum9 = 0

sum9 += ch

nine = repeat(0,9)

nine[ch] = ch

for sy=y*9 to y*9+18 by 9 do

~~for~~ sx=x to ~~x+2~~ do

end for

ch = board[sy+sx+1]-'0'

if sum9!=45 then return false end if

sum9 += ch

if nine!=nines then return false end if

nine[ch] = ch

end for

end for

end for

end for

return true

if sum9!=45 then return 0 end if

end function

if nine!=nines then return 0 end if

end for

function solve(string board)

end for

{sequence solution, sequence valid, integer solved} = plain_logic(board)

return 1

if solved=INVALID then return {{},INVALID} end if

end function

if solved=SOLVED then return {{solution},SOLVED} end if

if solved=BRUTE then return {{solution},BRUTE} end if

function solve(string board, sequence valid={})

if solved!=INCOMPLETE then ?9/0 end if

sequence solution, solutions

-- find the cell with the fewest options:

integer solved

-- (a possible improvement here would be to select the shortest

integer minopt, mindx

-- with the "most pairs" set, see swordfish etc above.)

object vi

integer minopt = 10, mindx

{solution,valid,solved} = plain_logic(board)

for i=1 to 9*9 do

if solved=INVALID then return {{},INVALID} end if

object vi = valid[i]

if solved=SOLVED then return {{solution},SOLVED} end if

if string(vi) then

if solved=BRUTE then return {{solution},BRUTE} end if

if length(vi)<=1 then ?9/0 end if -- should be caught above

if solved!=INCOMPLETE then ?9/0 end if

if length(vi)<minopt then

-- find the cell with the fewest options:

minopt = length(vi)

-- (a possible improvement here would be to select the shortest

mindx = i

-- with the "most pairs" set, see swordfish etc above.)

end if

minopt = 10

end if

for i=1 to 9*9 do

end for

vi = valid[i]

sequence solutions = {}

if string(vi) then

for i=1 to minopt do

if length(vi)<=1 then ?9/0 end if -- should be caught above

board[mindx] = valid[mindx][i]

if length(vi)<minopt then

{solution,solved} = solve(board)

minopt = length(vi)

if solved=MULTIPLE then

mindx = i

return {solution,MULTIPLE}

end if

elsif solved=SOLVED

end if

or solved=BRUTE then

end for

if not find(solution[1],solutions)

solutions = {}

and validate(solution[1]) then

for i=1 to minopt do

solutions = append(solutions,solution[1])

board[mindx] = valid[mindx][i]

end if

{solution,solved} = solve(board,valid)

if length(solutions)>1 then

if solved=MULTIPLE then

return {solutions,MULTIPLE}

return {solution,MULTIPLE}

elsif length(solutions) then

elsif solved=SOLVED

return {solutions,BRUTE}

or solved=BRUTE then

end if

if not find(solution[1],solutions)

end if

and validate(solution[1]) then

end for

solutions = append(solutions,solution[1])

if length(solutions)=1 then

end if

return {solutions,BRUTE}

if length(solutions)>1 then

end if

return {solutions,MULTIPLE}

return {{},INVALID}

elsif length(solutions) then

end function

return {solutions,BRUTE}

end if

function test_one(string board)

end if

{sequence solutions, integer solved} = solve(board)

end for

string solution, desc

if length(solutions)=1 then

if solved=SOLVED then

return {solutions,BRUTE}

desc = "(logic)"

end if

elsif solved=BRUTE then

return {{},INVALID}

desc = "(brute force)"

end function

else

desc = "???" -- INVALID/INCOMPLETE/MULTIPLE

function test_one(string board)

end if

sequence solutions

if length(solutions)=0 then

string solution, desc

solution = board

integer solved

desc = "*** NO SOLUTIONS ***"

{solutions,solved} = solve(board)

elsif length(solutions)=1 then

if solved=SOLVED then

solution = solutions[1]

desc = "(logic)"

if not validate(solution) then

elsif solved=BRUTE then

desc = "*** ERROR ***" -- (should never happen)

desc = "(brute force)"

end if

else

else

desc = "???" -- INVALID/INCOMPLETE/MULTIPLE

solution = board

end if

desc = "*** MULTIPLE SOLUTIONS ***"

if length(solutions)=0 then

end if

solution = board

return {solution,desc}

desc = "*** NO SOLUTIONS ***"

end function

elsif length(solutions)=1 then

solution = solutions[1]

--NB Blank cells can be represented by any character <'1'. Spaces are not recommended since

if not validate(solution) then

-- they can all too easily be converted to tabs by copy/paste/save. In particular, ? and

desc = "*** ERROR ***" -- (should never happen)

-- _ are NOT valid characters for representing a blank square. Use any of .0-* instead.

end if

~~else~~

constant tests = {

solution = board

"..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9", -- (0.01s, (logic))

desc = "*** MULTIPLE SOLUTIONS ***"

-- row/col elimination (was 8s w/o logic first)

end if

"000000036840000000000000020000203000010000700000600400000410050003000200600000000", -- (0.04s, (brute force))

return {solution,desc}

".......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....", -- (1.12s, (brute force))

end function

"000037600000600090008000004090000001600000009300000040700000800010009000002540000", -- (0.00s, (logic))

"....839..1......3...4....7..42.3....6.......4....7..1..2........8...92.....25...6", -- (0.04s, (brute force))

--NB Blank cells can be represented by any character <'1'. Spaces are not recommended since

"..1..5.7.92.6.......8...6...9..2.4.1.........3.4.8..9...7...3.......7.69.1.8..7..", -- (0.00s, (logic))

-- they can all too easily be converted to tabs by copy/paste/save. In particular, ? and

-- (the following takes ~8s when checking for multiple solutions)

-- _ are NOT valid characters for representing a blank square. Use any of .0-* instead.

"--3------4---8--36--8---1---4--6--73---9----------2--5--4-7--686--------7--6--5--", -- (0.01s, (brute force))

"..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..", -- (0.00s, (logic))

constant tests = {

"--4-5--6--6-1--8-93----7----8----5-----4-3-----6----7----2----61-5--4-3--2--7-1--", -- (0.00s, (logic))

"..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9", -- (0.01s, (logic))

-- x-wings

-- row/col elimination (was 8s w/o logic first)

".4398.25.6..425...2....1.949....4.7.3..6.8...41.2.9..382.5.........4...553489.71.", -- (0.00s, (logic))

"000000036840000000000000020000203000010000700000600400000410050003000200600000000", -- (0.04s, (brute force))

".......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....", -- (1.~~12s~~, (~~brute force~~))

".9...4..7.....79..8........4.58.....3.......2.....97.6........4..35.....2..6...8.", -- (0.00s, (logic))

-- "AL Escargot", so-called "hardest sudoku"

"000037600000600090008000004090000001600000009300000040700000800010009000002540000", -- (0.00s, (logic))

"....~~839~~..1......3...4....7..42.3....6.......4....7..1..2........8...92.....~~25...6~~", -- (0.~~04s~~, (brute force))

"1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..", -- (0.26s, (brute force))

"..1..5.7.92.6.......8...6...9..2.4.1.........3.4.8..9...7...3.......7.69.1.8..7..", -- (0.~~00s~~, (~~logic~~))

"12.3....435....1....4........54..2..6...7.........8.9...31..5.......9.7.....6...8", -- (0.48s, (brute force))

"12.4..3..3...1..5...6...1..7...9.....4.6.3.....3..2...5...8.7....7.....5.......98", -- (1.07s, (brute force))

-- (the following takes ~8s when checking for multiple solutions)

"394..267....3..4..5..69..2..45...9..6.......7..7...58..1..67..8..9..8....264..735", -- (0.00s, (logic))

"--3------4---8--36--8---1---4--6--73---9----------2--5--4-7--686--------7--6--5--", -- (0.01s, (brute force))

"..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..", -- (0.~~00s~~, (~~logic~~))

"4......6.5...8.9..3....1....2.7....1.9.....4.8....3.5....2....7..6.5...8.1......6", -- (0.01s, (brute force))

"5...7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79", -- (0.00s, (logic))

"--4-5--6--6-1--8-93----7----8----5-----4-3-----6----7----2----61-5--4-3--2--7-1--", -- (0.00s, (logic))

"503600009010002600900000080000700005006804100200003000030000008004300050800006702", -- (0.00s, (logic))

-- x-wings

".~~4398.25~~.6.~~.425~~...2....1.~~949~~....4.7.3..6.8...41.2.9..~~382~~.5.........4...~~553489~~.71.", -- (0.00s, (logic))

"53..247....2...8..1..7.39.2..8.72.49.2.98..7.79.....8.....3.5.696..1.3...5.69..1.", -- (0.00s, (logic))

"530070000600195000098000060800060003400803001700020006060000280000419005000080079", -- (0.00s, (logic))

".9...4..7.....79..8........4.58.....3.......2.....97.6........4..35.....2..6...8.", -- (0.00s, (logic))

-- set exclusion

-- "AL Escargot", so-called "hardest sudoku"

"1....7.9..3..2...8..96..5....53..9...1..8...26....4...3.....~~.1..4......7..7.~~..3..", -- (0.~~26s~~, (~~brute force~~))

"75..9..46961...3524.....79.2..6.1..7.8.....2.1..328.65.........3.9...2.484..3..79", -- (0.00s, (logic))

-- Worlds hardest sudoku:

"12.3....435....1....4........54..2..6...7.........8.9...31..5.......9.7.....6...8", -- (0.48s, (brute force))

"800000000003600000070090200050007000000045700000100030001000068008500010090000400", -- (0.21s, (brute force))

"12.4..3..3...1..5...6...1..7...9.....4.6.3.....3..2...5...8.7....7.....5.......98", -- (1.07s, (brute force))

"819--5-----2---75--371-4-6-4--59-1--7--3-8--2--3-62--7-5-7-921--64---9-----2--438", -- (0.00s, (logic))

"394..267....3..4..5..69..2..45...9..6.......7..7...58..1..67..8..9..8....264..735", -- (0.00s, (logic))

"4......6.5...8.9..3....1....2.7....1.9.....4.8....3.5....2....7..6.5...8.1......6", -- (0.01s, (~~brute force~~))

"85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.", -- (0.01s, (logic))

"5...7....6..~~195~~....98....6.8...6...34..8.3..17...2...6.6....28....~~419~~..5....8..79", -- (0.~~00s~~, (~~logic~~))

"9..2..5...4..6..3...3.....6...9..2......5..8...7..4..37.....1...5..2..4...1..6..9", -- (0.17s, (brute force))

"97.3...6..6.75.........8.5.......67.....3.....539..2..7...25.....2.1...8.4...73..", -- (0.00s, (logic))

"503600009010002600900000080000700005006804100200003000030000008004300050800006702", -- (0.00s, (logic))

-- "the beast" (an earlier algorithm took 318s (5min 18s) on this):

"53..247....2...8..1..7.39.2..8.72.49.2.98..7.79.....8.....3.5.696..1.3...5.69..1.", -- (0.00s, (logic))

"000060080020000000001000000070000102500030000000000400004201000300700600000000050", -- (0.03s, (brute force))

"530070000600195000098000060800060003400803001700020006060000280000419005000080079", -- (0.00s, (logic))

$},

-- set exclusion

"75..9..46961...3524.....79.2..6.1..7.8.....2.1..328.65.........3.9...2.484..3..79", -- (0.00s, (logic))

lt = length(tests),

-- Worlds hardest sudoku:

run_one_test = 0

"800000000003600000070090200050007000000045700000100030001000068008500010090000400", -- (0.21s, (brute force))

"819--5-----2---75--371-4-6-4--59-1--7--3-8--2--3-62--7-5-7-921--64---9-----2--438", -- (0.00s, (logic))

constant l = " x x x | x x x | x x x ",

"85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.", -- (0.01s, (logic))

s = "-------+-------+-------",

"9..2..5...4..6..3...3.....6...9..2......5..8...7..4..37.....1...5..2..4...1..6..9", -- (0.17s, (brute force))

l3 = join({l,l,l},"\n"),

"97.3...6..6.75.........8.5.......67.....3.....539..2..7...25.....2.1...8.4...73..", -- (0.00s, (logic))

fmt = substitute(join({l3,s,l3,s,l3},"\n"),"x","%c")&"\n"

-- "the beast" (an earlier algorithm took 318s (5min 18s) on this):

"000060080020000000001000000070000102500030000000000400004201000300700600000000050", -- (0.03s, (brute force))

procedure test()

$},

string board, -- (81 characters)

solution, desc

lt = length(tests),

atom t0 = time()

run_one_test = 0

if run_one_test then

board = tests[run_one_test]

constant l = " x x x | x x x | x x x ",

printf(1,fmt,board)

s = "-------+-------+-------",

{solution,desc} = test_one(board)

l3 = join({l,l,l},"\n"),

if length(solution)!=0 then

fmt = substitute(join({l3,s,l3,s,l3},"\n"),"x","%c")&"\n"

printf(1,"solution:\n")

printf(1,fmt,solution)

procedure print_board(string board)

end if

printf(1,fmt,board)

printf(1,"%s, %3.2fs\n",{desc,time()-t0})

end procedure

else

for i=1 to lt do

procedure test()

atom t1 = time()

string board -- (81 characters)

board = tests[i]

string solution, desc

{solution,desc} = test_one(board)

atom t0 = time()

printf(1," \"%s\", -- (%3.2fs, %s)\n",{board,time()-t1,desc})

if run_one_test then

-- printf(1," \"%s\", -- (%3.2fs, %s)\n",{solution,time()-t1,desc})

board = tests[run_one_test]

end for

print_board(board)

t0 = time()-t0

{solution,desc} = test_one(board)

printf(1,"%d puzzles solved in %3.2fs (av %3.2fs)\n",{lt,t0,t0/lt})

if length(solution)!=0 then

end if

printf(1,"solution:\n")

end procedure

print_board(solution)

test()

end if

printf(1,"%s, %3.2fs\n",{desc,time()-t0})

else

for i=1 to lt do

atom t1 = time()

board = tests[i]

{solution,desc} = test_one(board)

printf(1," \"%s\", -- (%3.2fs, %s)\n",{board,time()-t1,desc})

-- printf(1," \"%s\", -- (%3.2fs, %s)\n",{solution,time()-t1,desc})

end for

t0 = time()-t0

printf(1,"%d puzzles solved in %3.2fs (av %3.2fs)\n",{lt,t0,t0/lt})

end if

end procedure

test()</lang>

<pre>

Line 8,677:

Line 9,209:

=={{header|PHP}}==

<~~lang~~ php> class SudokuSolver {

<syntaxhighlight lang="php"> class SudokuSolver {

protected $grid = [];

protected $emptySymbol;

Line 8,801:

Line 9,333:

$solver = new SudokuSolver('009170000020600001800200000200006053000051009005040080040000700006000320700003900');

$solver->solve();

$solver->display();</~~lang~~>

$solver->display();</syntaxhighlight>

<pre>

Line 8,816:

Line 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>

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

<~~lang~~ ~~PicoLisp~~>(load "lib/simul.l")

<syntaxhighlight lang="picolisp">(load "lib/simul.l")

### Fields/Board ###

Line 8,900:

Line 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) ) )</~~lang~~>

(0 0 0 0 8 0 0 7 9) ) )</syntaxhighlight>

<pre> +---+---+---+---+---+---+---+---+---+

Line 8,922:

Line 9,558:

+---+---+---+---+---+---+---+---+---+

a b c d e f g h i</pre>

<pre> +---+---+---+---+---+---+---+---+---+

Line 8,947:

Line 9,583:

=={{header|PL/I}}==

Working PL/I version, derived from the Rosetta Fortran version.

<~~lang~~ pli>sudoku: procedure options (main); /* 27 July 2014 */

<syntaxhighlight lang="pli">sudoku: procedure options (main); /* 27 July 2014 */

declare grid (9,9) fixed (1) static initial (

Line 9,030:

Line 9,666:

end sudoku;

</syntaxhighlight>

</lang>

<pre>

Line 9,064:

Line 9,700:

Another PL/I version, reads sudoku from the text data file as 81 character record.

<~~lang~~ pli>

*PROCESS MARGINS(1,120) LIBS(SINGLE,STATIC);

*PROCESS OPTIMIZE(2) DFT(REORDER);

Line 9,203:

Line 9,839:

end sudoku;

</syntaxhighlight>

</lang>

=={{header|Prolog}}==

<~~lang~~ ~~Prolog~~>:- use_module(library(clpfd)).

<syntaxhighlight lang="prolog">:- use_module(library(clpfd)).

sudoku(Rows) :-

Line 9,231:

Line 9,867:

[5,_,_,_,_,_,_,7,3],

[_,_,2,_,1,_,_,_,_],

[_,_,_,_,4,_,_,_,9]]).</~~lang~~>

[_,_,_,_,4,_,_,_,9]]).</syntaxhighlight>

===GNU Prolog version===

<~~lang~~ ~~Prolog~~>:- initialization(main).

<syntaxhighlight lang="prolog">:- initialization(main).

Line 9,288:

Line 9,924:

main :- test(T), solve(T), maplist(show,T), halt.

show(X) :- write(X), nl.</~~lang~~>

show(X) :- write(X), nl.</syntaxhighlight>

<pre>[1,2,3,4,5,6,7,8,9]

Line 9,303:

Line 9,939:

=={{header|PureBasic}}==

A brute force method is used, it seemed the fastest as well as the simplest.

<~~lang~~ ~~PureBasic~~>DataSection

<syntaxhighlight lang="purebasic">DataSection

puzzle:

Data.s "394002670"

Line 9,413:

Line 10,049:

Input()

CloseConsole()

EndIf</~~lang~~>

EndIf</syntaxhighlight>

<pre>+-----+-----+-----+

Line 9,445:

Line 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

<~~lang~~ python>

def initiate():

box.append([0, 1, 2, 9, 10, 11, 18, 19, 20])

Line 9,531:

Line 10,169:

print grid[i*9:i*9+9]

raw_input()

</syntaxhighlight>

</lang>

===Search + Wave Function Collapse===

A Sudoku solver using search guided by the principles of wave function collapse.

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,540:

Line 10,245:

===Brute Force===

<lang ~~perl6~~>my @A = <

<syntaxhighlight lang="raku" line>my @A = <

5 3 0 0 2 4 7 0 0

0 0 2 0 0 0 8 0 0

Line 9,580:

Line 10,285:

}

solve;</~~lang~~>

solve;</syntaxhighlight>

Line 9,598:

Line 10,303:

This is an alternative solution that uses a more ellaborate set of choices instead of brute-forcing it.

<lang ~~perl6~~>#

<syntaxhighlight lang="raku" line>#

# 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,819:

Line 10,524:

}

}</~~lang~~>

}</syntaxhighlight>

Line 9,837:

Line 10,542:

A sudoku is represented as a matrix, see Rascal solutions to matrix related problems for examples.

<~~lang~~ ~~Rascal~~>import Prelude;

<syntaxhighlight lang="rascal">import Prelude;

import vis::Figure;

import vis::Render;

Line 9,920:

Line 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>

};</~~lang~~>

};</syntaxhighlight>

Example

Line 10,213:

Line 10,918:

Example of a back-tracking solver, from [[wp:Algorithmics of sudoku]]

<~~lang~~ ruby>def read_matrix(data)

<syntaxhighlight lang="ruby">def read_matrix(data)

lines = data.lines

9.times.collect { |i| 9.times.collect { |j| lines[i][j].to_i } }

Line 10,303:

Line 11,008:

print_matrix(matrix)

puts

print_matrix(solve_sudoku(matrix))</~~lang~~>

print_matrix(solve_sudoku(matrix))</syntaxhighlight>

Line 10,337:

Line 11,042:

=={{header|Rust}}==

<~~lang~~ rust>type Sudoku = [u8; 81];

<syntaxhighlight lang="rust">type Sudoku = [u8; 81];

fn is_valid(val: u8, x: usize, y: usize, sudoku_ar: &mut Sudoku) -> bool {

Line 10,400:

Line 11,105:

println!("Unsolvable");

}

}</~~lang~~>

}</syntaxhighlight>

Line 10,422:

Line 11,127:

Use CLP solver in SAS/OR:

<~~lang~~ sas>/* define SAS data set */

<syntaxhighlight lang="sas">/* define SAS data set */

data Indata;

input C1-C9;

Line 10,468:

Line 11,173:

/* print solution */

print X;

quit;</~~lang~~>

quit;</syntaxhighlight>

Output:

Line 10,489:

Line 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.

<~~lang~~ scala>object SudokuSolver extends App {

<syntaxhighlight lang="scala">object SudokuSolver extends App {

class Solver {

Line 10,620:

Line 11,325:

println(solution match {case Nil => "no solution!!!" case _ => f2Str(solution)})

}</~~lang~~>

}</syntaxhighlight>

<pre>riddle:

Line 10,654:

Line 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:

<~~lang~~ scala>object SudokuSolver extends App {

<syntaxhighlight lang="scala">object SudokuSolver extends App {

object Solver {

Line 10,771:

Line 11,476:

+("\n"*2))

}

}</~~lang~~>

}</syntaxhighlight>

<pre>riddle used in Ada section:

Line 10,902:

Line 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.

<lang>Init_board=[...

<syntaxhighlight lang="text">Init_board=[...

5 3 0 0 7 0 0 0 0;...

6 0 0 1 9 5 0 0 0;...

Line 11,074:

Line 11,779:

disp('Invalid solution found.');

disp_board(Solved_board);

end</~~lang~~>

end</syntaxhighlight>

Line 11,134:

Line 11,839:

=={{header|Sidef}}==

<~~lang~~ ruby>func check(i, j) is cached {

<syntaxhighlight lang="ruby">func check(i, j) is cached {

var (id, im) = i.divmod(9)

var (jd, jm) = j.divmod(9)

Line 11,182:

Line 11,887:

)

solve(grid)</~~lang~~>

solve(grid)</syntaxhighlight>

<pre>5 3 9 8 2 4 7 6 1

Line 11,197:

Line 11,902:

=={{header|Shale}}==

<~~lang~~ shale>

#!/usr/local/bin/shale

Line 11,727:

Line 12,432:

// I'd like to see an irregular sudoku with a knight's move constraint. Any takers...

</syntaxhighlight>

</lang>

'''Output'''

Line 11,768:

Line 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'''.

<~~lang~~ sql>with

<syntaxhighlight lang="sql">with

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,796:

Line 12,501:

from r

where pos = 0

;</~~lang~~>

;</syntaxhighlight>

A better (faster) approach - taking advantage of database-specific features - is to create a '''table''' NEIGHBORS (similar to the inline view in the WITH clause) and an index on column I of that table; then the query execution time drops by more than half in most cases.

Line 11,820:

Line 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.

<~~lang~~ stata>mata

<syntaxhighlight lang="stata">mata

function sudoku(a) {

s = J(81,20,.)

Line 11,920:

Line 12,625:

sudoku(a)

a

end</~~lang~~>

end</syntaxhighlight>

'''Output'''

Line 11,941:

Line 12,646:

Two more examples, from [http://www.7sudoku.com/very-difficult here] and [http://www.extremesudoku.info/sudoku.html there].

<~~lang~~ stata>a = 7,9,.,.,.,3,.,.,2\

<syntaxhighlight lang="stata">a = 7,9,.,.,.,3,.,.,2\

.,6,.,5,1,.,.,.,.\

.,.,.,.,.,2,.,.,6\

Line 11,993:

Line 12,698:

8 | 3 8 5 4 7 9 2 1 6 |

9 | 7 6 9 3 2 1 4 5 8 |

+-------------------------------------+</~~lang~~>

+-------------------------------------+</syntaxhighlight>

=={{header|Swift}}==

<~~lang~~ ~~Swift~~>import Foundation

<syntaxhighlight lang="swift">import Foundation

typealias SodukuPuzzle = [[Int]]

Line 12,120:

Line 12,825:

let puzzle = Soduku(board: board)

puzzle.solve()

puzzle.printBoard()</~~lang~~>

puzzle.printBoard()</syntaxhighlight>

<pre>

Line 12,140:

Line 12,845:

func solving(board: [[Int]]) -> [[Int]] {

var board = board

Line 12,205:

Line 12,910:

print(solving(board: puzzle))

</syntaxhighlight>

</lang>

<pre>

Line 12,224:

Line 12,929:

<~~lang~~ systemverilog>

//////////////////////////////////////////////////////////////////////////////

Line 12,354:

Line 13,059:

end

endprogram

</syntaxhighlight>

</lang>

It can be seen that SystemVerilog randomization is a very powerfull tool, in this implementation I directly described the game constraints and the randomization engine takes care of producing solutions, and when multiple solutions are possible they will be chosen at random.

Line 12,409:

Line 13,114:

=={{header|Tailspin}}==

There is a blog post about how this code was developed: https://tobega.blogspot.com/2020/05/creating-algorithm.html

templates deduceRemainingDigits

data row <"1">, col <"1"> local

templates findOpenPosition

@:{options: 10};

@:{options: 10"1"};

$ -> \[i;j](when <[](..~$@findOpenPosition.options)> do @findOpenPosition: {row: $i, col: $j, options: $::length}; \) -> !VOID

$ -> \[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,424:

Line 13,129:

when <[]?($i <=$pos.row>)

|[]?($j <=$pos.col>)

|[]?(($i-1)~/3 <=($pos.row-1)~/3>)?(($j-1)~/3 <=($pos.col-1)~/3>)> do [$... -> $when <~=$digit> do $! $] !

|[]?(($i::raw-1)~/3 <=($pos.row::raw-1)~/3>)?(($j::raw-1)~/3 <=($pos.col::raw-1)~/3>)> do [$... -> $when <~=$digit> do $! $] !

~~otherwise~~ $ !

when <> do $ !

\) !

end selectFirst

@: $;

$ -> findOpenPosition -> #

when <{options: <=0>}> do [] !

when <{options: <=0"1">}> do row´1:[] !

when <{options: <=10>}> do $@ !

when <{options: <=10"1">}> do $@ !

~~otherwise~~ def next: $;

when <> do def next: $;

$@ -> selectFirst&{pos: $next} -> deduceRemainingDigits

-> \(when <~=[]> do @deduceRemainingDigits: $; {options: 10} !

-> \(when <~=row´1:[]> do @deduceRemainingDigits: $; {options: 10"1"} !

when <=[]> do ^@deduceRemainingDigits($next.row;$next.col;1)

when <=row´1:[]> do ^@deduceRemainingDigits($next.row;$next.col;1)

-> { $next..., options: $next.options~~::raw~~-1} ! \) -> #

-> { $next..., options: $next.options-1"1"} ! \) -> #

end deduceRemainingDigits

test 'internal solver'

def sample: [

def sample: row´1:[

[5,3,4,6,7,8,9,1,2],

col´1:[5,3,4,6,7,8,9,1,2],

[6,7,2,1,9,5,3,4,8],

col´1:[6,7,2,1,9,5,3,4,8],

[1,9,8,3,4,2,5,6,7],

col´1:[1,9,8,3,4,2,5,6,7],

[8,5,9,7,6,1,4,2,3],

col´1:[8,5,9,7,6,1,4,2,3],

[4,2,6,8,5,3,7,9,1],

col´1:[4,2,6,8,5,3,7,9,1],

[7,1,3,9,2,4,8,5,6],

col´1:[7,1,3,9,2,4,8,5,6],

[9,6,1,5,3,7,2,8,4],

col´1:[9,6,1,5,3,7,2,8,4],

[2,8,7,4,1,9,6,3,5],

col´1:[2,8,7,4,1,9,6,3,5],

[3,4,5,2,8,6,1,7,9]

col´1:[3,4,5,2,8,6,1,7,9]

];

assert $sample -> deduceRemainingDigits <=$sample> 'completed puzzle unchanged'

assert [

assert row´1:[

[[5],3,4,6,7,8,9,1,2],

col´1:[[5],3,4,6,7,8,9,1,2],

$sample(2..last)...] -> deduceRemainingDigits <=$sample> 'final digit gets placed'

$sample(row´2..last)...] -> deduceRemainingDigits <=$sample> 'final digit gets placed'

assert [

assert row´1:[

[[],3,4,6,7,8,9,1,2],

col´1:[[],3,4,6,7,8,9,1,2],

$sample(2..last)...] -> deduceRemainingDigits <=[]> 'no remaining options returns empty'

$sample(row´2..last)...] -> deduceRemainingDigits <=row´1:[]> 'no remaining options returns empty'

assert [

assert row´1:[

[[5],3,4,6,[2,5,7],8,9,1,[2,5]],

col´1:[[5],3,4,6,[2,5,7],8,9,1,[2,5]],

$sample(2..last)...] -> deduceRemainingDigits <=$sample> 'solves 3 digits on row'

$sample(row´2..last)...] -> deduceRemainingDigits <=$sample> 'solves 3 digits on row'

assert [

assert row´1:[

[5,3,4,6,7,8,9,1,2],

col´1:[5,3,4,6,7,8,9,1,2],

[[6,7,9],7,2,1,9,5,3,4,8],

col´1:[[6,7,9],7,2,1,9,5,3,4,8],

[1,9,8,3,4,2,5,6,7],

col´1:[1,9,8,3,4,2,5,6,7],

[8,5,9,7,6,1,4,2,3],

col´1:[8,5,9,7,6,1,4,2,3],

[4,2,6,8,5,3,7,9,1],

col´1:[4,2,6,8,5,3,7,9,1],

[[7],1,3,9,2,4,8,5,6],

col´1:[[7],1,3,9,2,4,8,5,6],

[[7,9],6,1,5,3,7,2,8,4],

col´1:[[7,9],6,1,5,3,7,2,8,4],

[2,8,7,4,1,9,6,3,5],

col´1:[2,8,7,4,1,9,6,3,5],

[3,4,5,2,8,6,1,7,9]

col´1:[3,4,5,2,8,6,1,7,9]

] -> deduceRemainingDigits <=$sample> 'solves 3 digits on column'

assert [

assert row´1:[

[5,3,[4,6],6,7,8,9,1,2],

col´1:[5,3,[4,6],6,7,8,9,1,2],

[[6],7,2,1,9,5,3,4,8],

col´1:[[6],7,2,1,9,5,3,4,8],

[1,[4,6,9],8,3,4,2,5,6,7],

col´1:[1,[4,6,9],8,3,4,2,5,6,7],

$sample(4..last)...

$sample(row´4..last)...

] -> deduceRemainingDigits <=$sample> 'solves 3 digits in block'

// This gives a contradiction if 3 gets chosen out of [3,5]

assert [

assert row´1:[

[[3,5],[3,4,6],[3,4,6],[3,4,6],7,8,9,1,2],

col´1:[[3,5],[3,4,6],[3,4,6],[3,4,6],7,8,9,1,2],

$sample(2..last)...] -> deduceRemainingDigits <=$sample> 'contradiction is backtracked'

$sample(row´2..last)...] -> deduceRemainingDigits <=$sample> 'contradiction is backtracked'

end 'internal solver'

composer parseSudoku

[<section>=3]

row´1:[<section>=3]

rule section: <row>=3 (<'-+'>? <WS>?)

rule row: [<triple>=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,514:

Line 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(1;1) <=['5']> 'a digit'

assert $parsed(row´1;col´1) <=['5']> 'a digit'

assert $parsed(1;3) <=['1','2','3','4','5','6','7','8','9']> 'a dot'

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 <=[]> do 'No result found' !

when <=row´1:[]> do 'No result found' !

when <> do $ -> \[i](

'$(1..3)...;|$(4..6)...;|$(7..9)...;$#10;' !

'$(col´1..col´3)...;|$(col´4..col´6)...;|$(col´7..col´9)...;$#10;' !

$i -> $when <=3|=6> do '-----------$#10;' !$ !

$i -> $when <=row´3|=row´6> do '-----------$#10;' !$ !

\) -> '$...;' !

end solveSudoku

test 'sudoku solver'

assert

Line 12,556:

Line 13,261:

'> 'solves sudoku and outputs pretty solution'

end 'sudoku solver'

</syntaxhighlight>

</lang>

=={{header|Tcl}}==

Line 12,563:

Line 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}}

<~~lang~~ tcl>package require Tcl 8.6

<syntaxhighlight lang="tcl">package require Tcl 8.6

oo::class create Sudoku {

variable idata

Line 12,811:

Line 13,516:

return 0

}

}</~~lang~~>

}</syntaxhighlight>

Demonstration code:

<~~lang~~ tcl>SudokuSolver create sudoku

<syntaxhighlight lang="tcl">SudokuSolver create sudoku

sudoku load {

{3 9 4 @ @ 2 6 7 @}

Line 12,836:

Line 13,541:

}

sudoku destroy</~~lang~~>

sudoku destroy</syntaxhighlight>

<pre>+-----+-----+-----+

Line 12,852:

Line 13,557:

+-----+-----+-----+</pre>

If we'd added a logger method (after creating the <code>sudoku</code> object but before running the solver) like this:

<~~lang~~ tcl>oo::objdefine sudoku method Log msg {puts $msg}</~~lang~~>

<syntaxhighlight lang="tcl">oo::objdefine sudoku method Log msg {puts $msg}</syntaxhighlight>

Then this additional logging output would have been produced prior to the result being printed:

<pre>::RuleOnlyChoice solved ::sudoku at 8,0 for 1

Line 12,905:

Line 13,610:

Finished solving!</pre>

=={{header|Uiua}}==

Uses experimental '''⮌ orient''' and '''astar''' (only as a lazy way of managing the iteration :-).

# 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>

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

<~~lang~~ ~~Ursala~~>#import std

<syntaxhighlight lang="ursala">#import std

#import nat

Line 12,918:

Line 13,668:

~&rgg&& ~&irtPFXlrjrXPS; ~&lrK2tkZ2g&& ~&llrSL2rDrlPrrPljXSPTSL)+-,

//~&p ^|DlrDSLlrlPXrrPDSL(~&,num*+ rep2 block3)*= num block27 ~&iiK0 iota9,

* `0?=\~&iNC ! ~&t digits+-</~~lang~~>

* `0?=\~&iNC ! ~&t digits+-</syntaxhighlight>

test program:

<~~lang~~ ~~Ursala~~>#show+

<syntaxhighlight lang="ursala">#show+

example =

Line 12,935:

Line 13,685:

010067008

009008000

026400735]-</~~lang~~>

026400735]-</syntaxhighlight>

<pre>

Line 12,953:

Line 13,703:

=={{header|VBA}}==

<~~lang~~ VB>Dim grid(9, 9)

<syntaxhighlight lang="vb">Dim grid(9, 9)

Dim gridSolved(9, 9)

Line 13,054:

Line 13,804:

Debug.Print

Next i

End Sub</~~lang~~>

End Sub</syntaxhighlight>

<pre>

Line 13,073:

Line 13,823:

To run in console mode with cscript.

<~~lang~~ vb>Dim grid(9, 9)

<syntaxhighlight lang="vb">Dim grid(9, 9)

Dim gridSolved(9, 9)

Line 13,174:

Line 13,924:

End Sub 'Sudoku

Call sudoku</~~lang~~>

Call sudoku</syntaxhighlight>

<pre>Problem:

Line 13,196:

Line 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

'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

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

used=used Or pwr(x(row*9 + i))

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

'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

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)& " "

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>

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

=={{header|Wren}}==

<~~lang~~ ~~ecmascript~~>class Sudoku {

<syntaxhighlight lang="wren">class Sudoku {

construct new(rows) {

if (rows.count != 9 || rows.any { |r| r.count != 9 }) {

Line 13,276:

Line 14,184:

"000036040"

]

Sudoku.new(rows).solve()</~~lang~~>

Sudoku.new(rows).solve()</syntaxhighlight>

Line 13,313:

Line 14,221:

can be verified by several other examples.

<~~lang~~ ~~XPL0~~>code ChOut=8, CrLf=9, IntOut=11, Text=12;

<syntaxhighlight lang="xpl0">code ChOut=8, CrLf=9, IntOut=11, Text=12;

proc Show(X);

Line 13,383:

Line 14,291:

..9 ..8 ...

.26 4.. 735 ");

]</~~lang~~>

]</syntaxhighlight>

Line 13,402:

Line 14,310:

=={{header|zkl}}==

{{trans|C}} Note: Unlike in the C solution, 1<<-1 is defined (as 0).

<~~lang~~ zkl>fcn trycell(sdku,pos=0){

<syntaxhighlight lang="zkl">fcn trycell(sdku,pos=0){

row,col:=pos/9, pos%9;

Line 13,423:

Line 14,331:

sdku[pos]=0;

return(False);

}</~~lang~~>

}</syntaxhighlight>

<~~lang~~ zkl>problem:=

<syntaxhighlight lang="zkl">problem:=

#<<<

" 5 3 0 0 7 0 0 0 0

Line 13,442:

Line 14,350:

s[n*27,27].pump(Console.println,T(Void.Read,8),("| " + "%s%s%s | "*3).fmt); // 3 lines

println("+-----+-----+-----+");

}</~~lang~~>

}</syntaxhighlight>

<pre>