Sudoku: Difference between revisions

Solve a partially filled-in normal   9x9   [[wp:Sudoku|Sudoku]] grid   and display the result in a human-readable format.

 

<br><br>

 

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

{{works with|BBC BASIC for Windows}}

[[Image:sudoku_bbc.gif|right]]

*FONT Arial,28

ENDIF

NEXT

 

=={{header|BCPL}}==

// Implemented by Martin Richards.

 

// This is a really naive program to solve SuDoku problems. Even so it is usually quite fast.

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

 

{{trans|Java}}

 

class SudokuSolver

Console.Read();

}

using static System.Linq.Enumerable;

 

 

 

 

 

 

 

 

 

 

}

}

}

 

{{libheader|Microsoft Solver Foundation}}

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

 

namespace Sudoku

}

}

Produces:

<pre>

</pre>

 

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;

 

 

int main() {

ss.solve();

 

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

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

Given sud1.csv:

<pre>

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

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

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

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

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

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

8 2 6 | 4 1 9 | 7 3 5

</pre>

 

=={{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[][];

private boolean mColSubset[][];

private boolean mBoxSubset[][];

public Sudoku(int board[][]) {

mBoard = board;

mBoardSize = mBoard.length;

mBoxSize = (int)Math.sqrt(mBoardSize);

}

public void initSubsets() {

mRowSubset = new boolean[mBoardSize][mBoardSize];

}

}

private void setSubsetValue(int i, int j, int value, boolean present) {

mRowSubset[i][value - 1] = present;

mBoxSubset[computeBoxNo(i, j)][value - 1] = present;

}

public boolean solve() {

return solve(0, 0);

}

public boolean solve(int i, int j) {

if(i == mBoardSize) {

}

}

mBoard[i][j] = 0;

return false;

}

private boolean isValid(int i, int j, int val) {

val--;

return !isPresent;

}

private int computeBoxNo(int i, int j) {

int boxRow = i / mBoxSize;

return boxRow * mBoxSize + boxCol;

}

public void print() {

for(int i = 0; i < mBoardSize; i++) {

System.out.print("| ");

}

System.out.print(' ');

}

System.out.println("|");

}

System.out.println(" -----------------------");

}

 

 

 

=={{header|JavaScript}}==

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

5 9 8 | 7 3 6 | 2 4 1

</pre>

 

=={{header|Lua}}==

--based on a branch and bound solution

--fields are not tried in plain order

if x then

return printer(x)

Input:

<pre>

</pre>

Time with luajit: 9.245s

 

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

</pre>

 

{{out}}