Sudoku: Difference between revisions

{{trans|Kotlin}}

 

solved = 0B

grid = [0] * 81

‘000036040’]

 

 

{{out}}

 

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

\

\ Simple iterative backtracking Sudoku solver for 8th

"No solution!\n" .

then ;

 

=={{header|Ada}}==

{{trans|C++}}

with Ada.Text_IO;

 

solve( sudoku_ar );

end Sudoku;

 

{{out}}

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny].}}

{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}

MODE BOX = [3, 3]CHAR;

 

"__1__6__9"))

END CO

{{out}}

<pre>

 

=={{header|AutoHotkey}}==

SetBatchLines, -1

SetTitleMatchMode, 3

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

return r

 

=={{header|AWK}}==

# syntax: GAWK -f SUDOKU_RC.AWK

BEGIN {

}

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

{{out}}

<pre>

{{works with|BBC BASIC for Windows}}

[[Image:sudoku_bbc.gif|right]]

*FONT Arial,28

ENDIF

NEXT

 

=={{header|BCPL}}==

// Implemented by Martin Richards.

 

{ count := count + 1

prboard()

 

=={{header|Befunge}}==

Input should be provided as a sequence of 81 digits (optionally separated by whitespace), with zero representing an unknown value.

 

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

v<+>:0\`>v >\::9%:9+00p3/\9/:99++10p3/3*+39*+20p\:8+::00g\g2%\^

p|<$0.0^!g+:#9/9<^@ ^,>#+5<5_>#!<>#$0"------+-------+-----":#<^

<>v$v1:::0<>"P"`!^>0g#0v#p+9/9\%9:p04:\pg03g021pg03g011pg03g001

 

{{in}}

=={{header|Bracmat}}==

The program:

 

Solves any 9x9 sudoku, using backtracking.

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

& (puzzle..Display)$

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

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

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

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

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

Solution:

<pre>|~~~|~~~|~~~|

 

The following code is really only good for size 3 puzzles. A longer, even less readable version [[Sudoku/C|here]] could handle size 4s.

 

void show(int *x)

 

return 0;

 

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

===Backtracking===

{{trans|Java}}

 

class SudokuSolver

Console.Read();

}

 

=== Best First Search===

<!-- By Martin Freedman, 20/11/2021 -->

using static System.Linq.Enumerable;

using System.Collections.Generic;

}

}

Usage

using static System.Linq.Enumerable;

using static System.Console;

}

}

Output

<pre>693784512

{{libheader|Microsoft Solver Foundation}}

<!-- By Nigel Galloway, Jan 29, 2012 -->

 

namespace Sudoku

}

}

Produces:

<pre>

 

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

using System.Collections.Generic;

using System.Text;

 

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

{{out}}

<pre>

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

{{trans|Java}}

using namespace std;

 

ss.solve();

return EXIT_SUCCESS;

 

=={{header|Clojure}}==

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

 

(if (= x (dec c))

(recur ng 0 (inc y))

 

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

[0 0 0 3 0 0 4 0 0]

8 2 6 4 1 9 7 3 5

 

 

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

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

(dotimes (i 9 neighbors)

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

(setf (aref grid row column) choice)

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

Example:

<pre>> (defparameter *puzzle*

(7 5 9 2 3 8 1 4 6)

(8 2 6 4 1 9 7 3 5))</pre>

 

=={{header|Curry}}==

Copied from [http://www.informatik.uni-kiel.de/~curry/examples/ Curry: Example Programs].

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

---

" 5 7 921 ",

" 64 9 ",

 

 

{{Works with|PAKCS}}

Minimal w/o read or show utilities.

import Constraint (allC)

import List (transpose)

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

]

{{Out}}

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

{{trans|C++}}

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

std.ascii, std.typecons;

 

else

solution.get.representSudoku.writeln;

{{out}}

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

===Short Version===

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

 

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

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

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

{{out}}

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

===No-Heap Version===

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

 

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

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

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

Same output.

 

=={{header|Delphi}}==

Example taken from C++

TIntArray = array of Integer;

 

ShowMessage('Solved!');

end;

Usage:

SudokuSolver: TSudokuSolver;

begin

FreeAndNil(SudokuSolver);

end;

 

=={{header|EasyLang}}==

len grid[] 82

#

.

#

.

#

.

#

input_data

 

=={{header|Elixir}}==

{{trans|Erlang}}

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

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

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

 

{{out}}

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

 

display( Solved ),

io:nl().

{{out}}

<pre>

0 is the empty cell.

 

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

! risolve Sudoku: in input il file SUDOKU.TXT

 

 

 

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

===Backtracking===

<!-- By Martin Freedman, 26/11/2021 -->

 

//Helpers

/// solve sudoku using simple backtracking

'''Usage:'''

open SudokuBacktrack

 

printfn "Press any key to exit"

Console.ReadKey() |> ignore

{{Output}}<pre>

Puzzle:

===Constraint Satisfaction (Norvig)===

<!-- By Martin Freedman, 27/11/2021 -->

open System

 

 

/// 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 squares = cross rows cols

 

let unitlist =

[for c in cols -> cross rows [|c|] ]@

/// Dictionary of units for each square

let units =

/// Dictionary of all peer squares in the relevant units wrt square in question

let peers =

 

| 0 -> None

 

match values[s] |> Seq.contains d with

| false -> Some values // Already eliminated, nothing to do

| true ->

 

/// Convert grid into a Map of {square: char} with "0","."or"," for empties.

if Seq.length cells = 81 then cells |> Seq.zip squares |> Map.ofSeq |> Some else None

 

parsedGrid

 

/// Calculate string centre for each square - which can contain more than 1 digit when debugging

 

/// Display these values as a 2-D grid. Used for debugging

let asString = Seq.map string >> String.concat ""

let width = 1 + ([for s in squares do Seq.length values[s]] |> List.max)

[for r in rows do

for c in cols do

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

 

/// Using depth-first search and propagation, try all possible values.

[for s in squares do if Seq.length values[s] > 1 then Seq.length values[s] ,s]

|> function

| [] -> Some values // Solved!

 

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

open System.Diagnostics

open System.IO

printfn "Try again with search:"

simple |> solveWithSearch |> printfn "%s"

if Seq.length argv = 1 then

let num = argv[0] |> int

File.ReadLines(@"sudoku17.txt") |> Seq.take num |>Array.ofSeq

else

File.ReadLines(@"sudoku17.txt") |>Array.ofSeq

watch.Start()

if result |> Seq.forall Option.isSome then

let total = watch.ElapsedMilliseconds

else

printfn "Some sudoku17 puzzles failed"

Console.ReadKey() |> ignore

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

 

Try again with search:

4 1 7 |3 6 9 |8 2 5

6 3 2 |1 5 8 |9 4 7

5 9 8 |7 3 6 |2 4 1

 

 

 

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

List.map2(fun n g->List.map(fun(n',g')->((n',g'),n))g) (List.rev n) g|>List.concat|>List.sortBy (fun ((_,n),_)->n)|>List.groupBy(fun ((n,_),_)->n)|>List.sortBy(fun(n,_)->n)

|>List.iter(fun (_,n)->n|>Seq.fold(fun z ((_,g),v)->[z..g-1]|>Seq.iter(fun _->printf " |");printf "%s|" v; g+1 ) 0 |>ignore;printfn "")

'''Usage:'''

Given sud1.csv:

</pre>

then

let n=SLPsolve (fE ([1..9]|>List.map(string)) 9 3 3 "sud1.csv")

printSLP ([1..9]|>List.map(string)) (Seq.item 0 n)

{{out}}

<pre>

=={{header|Forth}}==

{{works with|4tH|3.60.0}}

include lib/istype.4th

include lib/argopen.4th

;

 

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

This implementation uses a brute force method. The subroutine <code>solve</code> recursively checks valid entries using the rules defined in the function <code>is_safe</code>. When <code>solve</code> is called beyond the end of the sudoku, we know that all the currently entered values are valid. Then the result is displayed.

 

implicit none

end subroutine pretty_print

 

{{out}}<pre>

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

=={{header|FreeBASIC}}==

{{trans|VBA}}

 

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

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

Next i

{{out}}

<pre>

=={{header|FutureBasic}}==

First is a short version:

include "Util_Containers.incl"

 

begin globals

end globals

 

BeginCDeclaration

EndC

 

BeginCFunction

{

{

}

EndC

 

toolbox fn print_sudoku() = CFMutableStringRef

 

 

gC = " "

print : print "Sudoku solved:" : print

if ( solution )

else

end if

 

Output:

More code in this one, but faster execution:

<pre>

begin globals

_digits = 9

 

begin record Board

end record

 

end globals

 

 

local mode

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

end fn

 

local fn prepare( b as ^Board )

end fn

 

local fn printBoard( b as ^Board )

end fn

 

local fn verifica( b as ^Board )

end fn = check

 

 

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

end fn = check

 

 

local fn solve( b as ^Board )

end fn = check

 

 

local fn resolve( b as ^Board )

end fn = check

 

 

fn prepare( @quiz )

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

 

for i = 1 to _digits

next i

 

fn printBoard( @quiz )

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

 

check = fn resolve(@quiz)

 

if ( check )

else

end if

fn printBoard( @quiz )

</pre>

 

Input to function solve is an 81 character string.

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

 

import "fmt"

}

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

{{out}}

<pre>

 

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

'Solution:'

;'2 8 4 3 7 5 1 6 9

 

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

 

=={{header|Groovy}}==

 

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

class GridException extends Exception {

}

grid

'''Test/Benchmark Cases'''

 

Mentions of ''"exceptionally difficult" example in Wikipedia'' refer to this (former) page: [[https://en.wikipedia.org/w/index.php?title=Sudoku_solving_algorithms&oldid=410240496#Exceptionally_difficult_Sudokus_.28hardest_Sudokus.29 Exceptionally difficult Sudokus]]

//Used in Curry solution: ~ 0.1 seconds

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

solution.each { println it }

println "\nELAPSED: ${elapsed} seconds"

 

{{out}} (last only):

 

=={{header|Java}}==

{

private int mBoard[][];

}

}

 

{{out}}

====ES6====

 

/**

* The doubly-doubly circularly linked data object.

search(H, []);

};

 

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

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

reduceGrid(s);

 

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

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

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

</pre>

 

=={{header|Julia}}==

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

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

for i in 1:81

if grid[i] == 0

 

for j in 1:81

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

 

{{out}}

<pre>

=={{header|Kotlin}}==

{{trans|C++}}

 

class Sudoku(rows: List<String>) {

)

Sudoku(rows).solve()

 

{{out}}

=={{header|Lua}}==

===without FFI, slow===

--based on a branch and bound solution

--fields are not tried in plain order

if x then

return printer(x)

Input:

<pre>

Time with luajit: 9.245s

===with FFI, fast===

ffi=require"ffi"

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

... .8. .79

]])

{{out}}

<pre>> time ./sudoku_fast.lua

 

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

NestWhile[

Join @@ Table[

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

Position[s, 0, {2}],

Example:

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

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

{7, 0, 0, 0, 2, 5, 0, 0, 0},

{0, 0, 2, 0, 1, 0, 0, 0, 8},

{{out}}

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

 

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

 

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

%% End of program

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

All empty cells must have a value of NaN.

1 NaN NaN NaN NaN NaN NaN 3 NaN

NaN NaN 4 NaN NaN NaN NaN 7 NaN

NaN 2 NaN NaN NaN NaN NaN NaN NaN

NaN 8 NaN NaN NaN 9 2 NaN NaN

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

 

7 6 5 4 8 3 9 2 1

9 2 6 1 4 7 5 8 3

5 8 1 3 6 9 2 4 7

 

=={{header|Nim}}==

{{trans|Kotlin}}

 

type

var puzzle = Sudoku()

puzzle.init(rows)

 

{{out}}

=={{header|OCaml}}==

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

Copyright 2004-2007 Sylvain Conchon, Jean-Christophe Filliatre, Julien Signoles

 

module C = Coloring.Mark(G)

 

 

=={{header|Oz}}==

Using built-in constraint propagation and search.

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

fun {Puzzle1}

end

in

 

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

 

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

 

typedef int SUDOKU [9][9];

return gen_0; /* no solution */

}

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

 

Install plugin from home directory and play:

 

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

{{works with|Free Pascal}}

Simple backtracking implimentation, therefor it must be fast to be competetive.With doReverse = true same sequence for trycell. nearly 5 times faster than [[Sudoku#C|C]]-Version.

{$IFDEF FPC}

{$CODEALIGN proc=16,loop=8}

Outfield(solF);

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

{{out}}

<pre>

 

=={{header|Perl}}==

use integer;

use strict;

}

}

{{out}}

<pre>

=={{header|Phix}}==

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

{{out}}

<pre>

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

{{out}}

<pre>

=={{header|PHP}}==

{{trans|C++}}

protected $grid = [];

protected $emptySymbol;

$solver = new SudokuSolver('009170000020600001800200000200006053000051009005040080040000700006000320700003900');

$solver->solve();

{{out}}

<pre>

7 8 2 | 5 6 3 | 9 1 4

(solved in 0.027s)

</pre>

 

=={{header|PicoLisp}}==

 

### Fields/Board ###

(0 6 0 0 0 0 2 8 0)

(0 0 0 4 1 9 0 0 5)

{{out}}

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

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

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

{{out}}

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

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

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

 

declare grid (9,9) fixed (1) static initial (

 

end sudoku;

{{out}}

<pre>

 

Another PL/I version, reads sudoku from the text data file as 81 character record.

*PROCESS MARGINS(1,120) LIBS(SINGLE,STATIC);

*PROCESS OPTIMIZE(2) DFT(REORDER);

 

end sudoku;

 

=={{header|Prolog}}==

sudoku(Rows) :-

[5,_,_,_,_,_,_,7,3],

[_,_,2,_,1,_,_,_,_],

 

===GNU Prolog version===

{{works with|GNU Prolog|1.4.4}}

 

 

 

main :- test(T), solve(T), maplist(show,T), halt.

{{Out}}

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

=={{header|PureBasic}}==

A brute force method is used, it seemed the fastest as well as the simplest.

puzzle:

Data.s "394002670"

Input()

CloseConsole()

{{out}}

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

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

 

A simple backtrack algorithm -- Quick but may take longer if the grid had been more than 9 x 9

def initiate():

box.append([0, 1, 2, 9, 10, 11, 18, 19, 20])

print grid[i*9:i*9+9]

raw_input()

 

=={{header|Racket}}==