Rosetta Code

Sudoku: Difference between revisions

Page Discussion

Sudoku (view source)

Revision as of 22:53, 28 June 2024

4,032 bytes added ,  6 days ago
Added Uiua solution
m (→‎{{header|FutureBasic}}: remove 'dim as' and update millisecond timer)
(Added Uiua solution)
 
(10 intermediate revisions by 4 users not shown)
Line 3,200:
.
.
call init
#
proc display . .
Line 3,223:
if pos > 81
# solved
call display
break 1return
.
r = (pos - 1) div 9
Line 3,238:
col[c + d] = 1
box[b + d] = 1
call solve pos + 1
row[r + d] = 0
col[c + d] = 0
Line 3,246:
grid[pos] = 0
.
call solve 1
#
input_data
Line 3,260:
9 6 0 0 1 0 3 0 0
0 5 0 6 9 0 0 1 0
 
</syntaxhighlight>
 
Line 5,157 ⟶ 5,158:
First is a short version:
<syntaxhighlight lang="futurebasic">
include "NSLog.incl"
include "Util_Containers.incl"
 
begin globals
dim as 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;
ccfor (i = c/30; *i 3< +9; i%3;++)
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 (i solve_sudoku(!= c && sudoku[r][i)] == sudoku[r][c]) return -10;
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-1;
}
 
 
short solve_sudoku( short i )
CFMutableStringRef print_sudoku()
{
short ir, jc;
CFMutableStringRef mutStr;
if (i < 0) return 0;
mutStr = CFStringCreateMutable( kCFAllocatorDefault, 0 );
else if (i >= 81) return -1;
 
for (i = 0; i < 9; i++)
r {= i / 9;
for (jc = 0;i j <% 9; j++)
{
if (sudoku[r][c])
CFStringAppendFormat( mutStr, NULL, (CFStringRef)@" %d", sudoku[i][j] );
return check_sudoku(r, c) && solve_sudoku(i + 1);
}
else
CFStringAppendFormat( mutStr, NULL, (CFStringRef)@"\r" );
for (sudoku[r][c] = 9; sudoku[r][c] > 0; sudoku[r][c]--)
}
{
return( mutStr );
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 5,244:
toolbox fn print_sudoku() = CFMutableStringRef
 
dim as short solution
dim as CFMutableStringRef cfRef
 
gC = " "
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
 
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
Line 10,168 ⟶ 10,170:
raw_input()
</syntaxhighlight>
 
===Search + Wave Function Collapse===
 
A Sudoku solver using search guided by the principles of wave function collapse.
<syntaxhighlight lang="python">
 
 
sudoku = [
# cell value # cell number
0, 0, 4, 0, 5, 0, 0, 0, 0, # 0, 1, 2, 3, 4, 5, 6, 7, 8,
9, 0, 0, 7, 3, 4, 6, 0, 0, # 9, 10, 11, 12, 13, 14, 15, 16, 17,
0, 0, 3, 0, 2, 1, 0, 4, 9, # 18, 19, 20, 21, 22, 23, 24, 25, 26,
0, 3, 5, 0, 9, 0, 4, 8, 0, # 27, 28, 29, 30, 31, 32, 33, 34, 35,
0, 9, 0, 0, 0, 0, 0, 3, 0, # 36, 37, 38, 39, 40, 41, 42, 43, 44,
0, 7, 6, 0, 1, 0, 9, 2, 0, # 45, 46, 47, 48, 49, 50, 51, 52, 53,
3, 1, 0, 9, 7, 0, 2, 0, 0, # 54, 55, 56, 57, 58, 59, 60, 61, 62,
0, 0, 9, 1, 8, 2, 0, 0, 3, # 63, 64, 65, 66, 67, 68, 69, 70, 71,
0, 0, 0, 0, 6, 0, 1, 0, 0, # 72, 73, 74, 75, 76, 77, 78, 79, 80
# zero = empty.
]
 
numbers = {1,2,3,4,5,6,7,8,9}
 
def options(cell,sudoku):
""" determines the degree of freedom for a cell. """
column = {v for ix, v in enumerate(sudoku) if ix % 9 == cell % 9}
row = {v for ix, v in enumerate(sudoku) if ix // 9 == cell // 9}
box = {v for ix, v in enumerate(sudoku) if (ix // (9 * 3) == cell // (9 * 3)) and ((ix % 9) // 3 == (cell % 9) // 3)}
return numbers - (box | row | column)
 
initial_state = sudoku[:] # the sudoku is our initial state.
 
job_queue = [initial_state] # we need the jobqueue in case of ambiguity of choice.
 
while job_queue:
state = job_queue.pop(0)
if not any(i==0 for i in state): # no missing values means that the sudoku is solved.
break
 
# determine the degrees of freedom for each cell.
degrees_of_freedom = [0 if v!=0 else len(options(ix,state)) for ix,v in enumerate(state)]
# find cell with least freedom.
least_freedom = min(v for v in degrees_of_freedom if v > 0)
cell = degrees_of_freedom.index(least_freedom)
 
for option in options(cell, state): # for each option we add the new state to the queue.
new_state = state[:]
new_state[cell] = option
job_queue.append(new_state)
 
# finally - print out the solution
for i in range(9):
print(state[i*9:i*9+9])
 
# [2, 6, 4, 8, 5, 9, 3, 1, 7]
# [9, 8, 1, 7, 3, 4, 6, 5, 2]
# [7, 5, 3, 6, 2, 1, 8, 4, 9]
# [1, 3, 5, 2, 9, 7, 4, 8, 6]
# [8, 9, 2, 5, 4, 6, 7, 3, 1]
# [4, 7, 6, 3, 1, 8, 9, 2, 5]
# [3, 1, 8, 9, 7, 5, 2, 6, 4]
# [6, 4, 9, 1, 8, 2, 5, 7, 3]
# [5, 2, 7, 4, 6, 3, 1, 9, 8]
 
</syntaxhighlight>
 
This solver found the 45 unknown values in 45 steps.
 
=={{header|Racket}}==
Line 13,541 ⟶ 13,610:
Finished solving!</pre>
 
=={{header|Uiua}}==
{{Works with |Uiua|0.12.0-dev.1}}
Uses experimental '''⮌ orient''' and '''astar''' (only as a lazy way of managing the iteration :-).
<syntaxhighlight lang="uiua">
# Solves Sudoku using brute force.
# Experimental!
S ← [[8 5 0 0 0 2 4 0 0]
[7 2 0 0 0 0 0 0 9]
[0 0 4 0 0 0 0 0 0]
[0 0 0 1 0 7 0 0 2]
[3 0 5 0 0 0 9 0 0]
[0 4 0 0 0 0 0 0 0]
[0 0 0 0 8 0 0 7 0]
[0 1 7 0 0 0 0 0 0]
[0 0 0 0 3 6 0 4 0]]
Ps ← ⊞⊟.⇡9
Boxes ← ↯∞_9_2 ⊡⊞⊂.0_3_6 ◫3_3Ps
Nines ← ⊂Boxes⊂⟜(⮌1_0)Ps # 27 lists of pos's: one per row, col, box.
IsIn ← ☇1▽:⟜≡(∊:)Nines ¤ # (pos) -> pos's of all peers for a pos.
Peers ← ⊞(IsIn ⊟).⇡9 # For each pos, the pos of every peer (by row, col, box)
 
Free ← ▽:⟜(¬∊)+1⇡9◴▽⊸(>0)⊡⊡:Peers # Free values at pos (pos board) -> [n]
Next ← (
=/↧.≡(⧻Free) ⊙¤,,⊚=0. # Find most constrained pos.
Free,,⊙◌⊢▽⊙. # Get free values at pos.
≡(⍜⊡⋅∘)λBCa # Generate node for each.
)
End ← =0/+/+=0
astar(⍣Next⋅[]|0|End)S
↙¯1°□⊢⊙◌
</syntaxhighlight>
{{out}}
<pre>
╭─
╷ 8 5 1 3 9 2 4 6 7
╷ 7 2 3 4 6 1 5 8 9
6 9 4 7 5 8 2 3 1
9 6 8 1 4 7 3 0 2
3 0 5 0 0 0 9 0 0
0 4 0 0 0 0 0 0 0
0 0 0 0 8 0 0 7 0
0 1 7 0 0 0 0 0 0
0 0 0 0 3 6 0 4 0
╯
</pre>
=={{header|Ursala}}==
<syntaxhighlight lang="ursala">#import std
Line 13,993 ⟶ 14,107:
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="ecmascriptwren">class Sudoku {
construct new(rows) {
if (rows.count != 9 || rows.any { |r| r.count != 9 }) {
Midaz
163

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/349797...365855"