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*

Based on the Java implementation presented in the video "[https://www.youtube.com/watch?v=mcXc8Mva2bA Create a Sudoku Solver In Java...]".

 

 

def isNumberInRow(board, number, row)

printBoard(board)

end

{{out}}

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

// using array O(1) lookup & mutable instead of map O(logn) immutable - now 6 times faster

module SudokuCPSArray

let solveNoSearch: string -> string = solver applyCPS

let solveWithSearch: string -> string = solver (applyCPS >> (Option.bind search))

open SudokuCPSArray

open System.Diagnostics

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

 

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

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #004080;">sequence</span> <span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"""

<span style="color: #000000;">brute_solve</span><span style="color: #0000FF;">()</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n(solved in %3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span>

{{out}}

<pre>

contains 339 puzzles, can be run as a command-line or gui program, check for multiple solutions, and produce

a more readable single-puzzle output (example below).

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #000080;font-style:italic;">-- Working directly on 81-character strings ultimately proves easier: Originally I

<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>

<span style="color: #000000;">test</span><span style="color: #0000FF;">()</span>

{{out}}

<pre>

=={{header|PHP}}==

{{trans|C++}}

protected $grid = [];

protected $emptySymbol;

$solver = new SudokuSolver('009170000020600001800200000200006053000051009005040080040000700006000320700003900');

$solver->solve();

{{out}}

<pre>

Using constraint programming.

 

import cp.

 

end,

nl.

 

sudoku(Board) =>

end,

solve([ffd,inout], Vars).

 

print_board(Board) =>

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

 

<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

 

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

===Brute Force===

{{trans|Perl}}

5 3 0 0 2 4 7 0 0

0 0 2 0 0 0 8 0 0

}

}

 

{{out}}

This is an alternative solution that uses a more ellaborate set of choices instead of brute-forcing it.

 

# In this code, a sudoku puzzle is represented as a two-dimentional

# array. The cells that are not yet solved are represented by yet

}

}

 

{{out}}

A sudoku is represented as a matrix, see Rascal solutions to matrix related problems for examples.

 

import vis::Figure;

import vis::Render;

<0,7,0>, <1,7,0>, <2,7,9>, <3,7,0>, <4,7,0>, <5,7,8>, <6,7,0>, <7,7,0>, <8,7,0>,

<0,8,0>, <1,8,2>, <2,8,6>, <3,8,4>, <4,8,0>, <5,8,0>, <6,8,7>, <7,8,3>, <8,8,5>

 

Example

Example of a back-tracking solver, from [[wp:Algorithmics of sudoku]]

{{works with|Ruby|2.0+}}

lines = data.lines

9.times.collect { |i| 9.times.collect { |j| lines[i][j].to_i } }

print_matrix(matrix)

puts

 

{{out}}

=={{header|Rust}}==

{{trans|Ada}}

 

fn is_valid(val: u8, x: usize, y: usize, sudoku_ar: &mut Sudoku) -> bool {

println!("Unsolvable");

}

 

{{out}}

Use CLP solver in SAS/OR:

 

data Indata;

input C1-C9;

/* print solution */

print X;

 

Output:

This solver works with normally 9x9 sudokus as well as with sudokus of jigsaw type or sudokus with additional condition like diagonal constraint.

{{works with|Scala|2.9.1}}

 

class Solver {

println(solution match {case Nil => "no solution!!!" case _ => f2Str(solution)})

{{out}}

<pre>riddle:

The implementation above doesn't work so effective for sudokus like Bracmat version, therefore I implemented a second version inspired by Java section:

{{works with|Scala|2.9.1}}

 

object Solver {

+("\n"*2))

}

{{out}}

<pre>riddle used in Ada section:

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.

 

5 3 0 0 7 0 0 0 0;...

6 0 0 1 9 5 0 0 0;...

disp('Invalid solution found.');

disp_board(Solved_board);

 

{{out}}

=={{header|Sidef}}==

{{trans|Raku}}

var (id, im) = i.divmod(9)

var (jd, jm) = j.divmod(9)

)

 

{{out}}

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

 

=={{header|Shale}}==

#!/usr/local/bin/shale

 

 

// I'd like to see an irregular sudoku with a knight's move constraint. Any takers...

 

'''Output'''

The input and output are presented as strings of 81 characters, where each character is either a digit or a space (indicating an empty cell in the grid). The translation between grids and such strings is trivial (convert grid to string by concatenating rows, reading left to right and then top to bottom), and not covered in the solution. The input is given as a bind variable, ''':game'''.

 

symbols (d) as (select to_char(level) from dual connect by level <= 9)

, board (i) as (select level from dual connect by level <= 81)

from r

where pos = 0

 

A better (faster) approach - taking advantage of database-specific features - is to create a '''table''' NEIGHBORS (similar to the inline view in the WITH clause) and an index on column I of that table; then the query execution time drops by more than half in most cases.

The example grid given below is taken from [https://en.wikipedia.org/wiki/Sudoku_solving_algorithms Wikipedia]. It does not require any recursive call (it's entirely filled in the first step of ''solve''), as can be seen with additional ''printf'' in the code to follow the algorithm.

 

function sudoku(a) {

s = J(81,20,.)

sudoku(a)

a

 

'''Output'''

Two more examples, from [http://www.7sudoku.com/very-difficult here] and [http://www.extremesudoku.info/sudoku.html there].

 

.,6,.,5,1,.,.,.,.\

.,.,.,.,.,2,.,.,6\

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

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

 

=={{header|Swift}}==

{{trans|Java}}

 

typealias SodukuPuzzle = [[Int]]

let puzzle = Soduku(board: board)

puzzle.solve()

{{out}}

<pre>

{{works with|Swift 3}}

 

func solving(board: [[Int]]) -> [[Int]] {

var board = board

 

print(solving(board: puzzle))

{{out}}

<pre>

 

 

 

//////////////////////////////////////////////////////////////////////////////

end

endprogram

 

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.

 

=={{header|Tailspin}}==

templates deduceRemainingDigits

templates findOpenPosition

$@ !

end findOpenPosition

templates selectFirst&{pos:}

def digit: $($pos.row;$pos.col) -> $(1);

when <[]?($i <=$pos.row>)

|[]?($j <=$pos.col>)

\) !

end selectFirst

@: $;

$ -> findOpenPosition -> #

$@ -> selectFirst&{pos: $next} -> deduceRemainingDigits

end deduceRemainingDigits

test 'internal solver'

];

assert $sample -> deduceRemainingDigits <=$sample> 'completed puzzle unchanged'

] -> deduceRemainingDigits <=$sample> 'solves 3 digits on column'

] -> deduceRemainingDigits <=$sample> 'solves 3 digits in block'

// This gives a contradiction if 3 gets chosen out of [3,5]

end 'internal solver'

composer parseSudoku

rule section: <row>=3 (<'-+'>? <WS>?)

rule triple: <digit|dot>=3 (<'\|'>?)

rule digit: [<'\d'>]

rule dot: <'\.'> -> [1..9 -> '$;']

end parseSudoku

test 'input sudoku'

def parsed:

...|419|..5

...|.8.|.79' -> parseSudoku;

assert $parsed <[<[<[]>=9](9)>=9](9)> 'parsed sudoku has 9 rows containing 9 columns of lists'

end 'input sudoku'

templates solveSudoku

$ -> parseSudoku -> deduceRemainingDigits -> #

when <> do $ -> \[i](

\) -> '$...;' !

end solveSudoku

test 'sudoku solver'

assert

'> 'solves sudoku and outputs pretty solution'

end 'sudoku solver'

 

=={{header|Tcl}}==

Note that you can implement more rules if you want. Just make another subclass of <code>Rule</code> and the solver will pick it up and use it automatically.

{{works with|Tcl|8.6}} or {{libheader|TclOO}}

oo::class create Sudoku {

variable idata

return 0

}

Demonstration code:

sudoku load {

{3 9 4 @ @ 2 6 7 @}

}

}

{{out}}

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

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

If we'd added a logger method (after creating the <code>sudoku</code> object but before running the solver) like this:

Then this additional logging output would have been produced prior to the result being printed:

<pre>::RuleOnlyChoice solved ::sudoku at 8,0 for 1

 

=={{header|Ursala}}==

#import nat

 

~&rgg&& ~&irtPFXlrjrXPS; ~&lrK2tkZ2g&& ~&llrSL2rDrlPrrPljXSPTSL)+-,

//~&p ^|DlrDSLlrlPXrrPDSL(~&,num*+ rep2 block3)*= num block27 ~&iiK0 iota9,

test program:

 

example =

010067008

009008000

{{out}}

<pre>

=={{header|VBA}}==

{{trans|Fortran}}

Dim gridSolved(9, 9)

 

Debug.Print

Next i

{{out}}

<pre>

{{trans|VBA}}

To run in console mode with cscript.

Dim gridSolved(9, 9)

End Sub 'Sudoku

 

{{out}}

<pre>Problem:

2 4 3 1 5 7 8 6 9

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

 

=={{header|Wren}}==

{{trans|Kotlin}}

construct new(rows) {

if (rows.count != 9 || rows.any { |r| r.count != 9 }) {

"000036040"

]

 

{{out}}

can be verified by several other examples.

{{trans|C}}

 

proc Show(X);

..9 ..8 ...

.26 4.. 735 ");

 

{{out}}

=={{header|zkl}}==

{{trans|C}} Note: Unlike in the C solution, 1<<-1 is defined (as 0).

row,col:=pos/9, pos%9;

sdku[pos]=0;

return(False);

#<<<

" 5 3 0 0 7 0 0 0 0

s[n*27,27].pump(Console.println,T(Void.Read,8),("| " + "%s%s%s | "*3).fmt); // 3 lines

println("+-----+-----+-----+");

{{out}}

<pre>