Download or view Sudoku.frink in plain text format
// Sudoku solver class.
// The board is a 9x9 array, each element of which is a set which contains
// the possible values for that cell. The values in each cell are expected
// to be the integers 1 through 9.
//
class Sudoku
{
var board;
// Constructor; creates a board with no items yet set.
new[] :=
{
board = new array[8]
for row = 0 to 8
{
thisrow = board@row = new array[]
for col = 0 to 8
{
thisset = thisrow@col = new set
for n = 1 to 9
thisset.put[n]
}
}
}
// Create a new board from a 2-dimensional array of values, like the
// following:
//
// c=["----19-4-",
// "--48--6--",
// "75------2",
// "-9-1-2--4",
// "-----3---",
// "5--4-6-3-",
// "8------73",
// "--6--84--",
// "-1-29----"]
// b = Sudoku.createFromArray[c]
// b.solve[]
// b.dump[]
//
// Any character other than [1-9] can be used for the "placeholder"
// character.
// Note that this will automatically begin to simplify the
class createFromArray[array] :=
{
b = new Sudoku
for row=0 to 8
{
r = array@row
for col=0 to 8
{
c = substrLen[r, col, 1]
if c >= "1" and c <= "9"
b.setNoCheck[row, col, parseInt[c]]
}
}
return b
}
// Prints a representation of the current state of the solution.
dump[] :=
{
for row = 0 to 8
{
for col = 0 to 8
{
dumpCell[board@row@col]
if col != 8
print["|"]
}
println[]
}
println[]
}
dumpCell[cell] :=
{
for n = 1 to 9
if cell.contains[n]
print[n]
else
print[" "]
}
// Internal set method
setNoCheck[row, col, value] :=
{
x = new set
x.put[value]
board@row@col = x
// Remove all instances of that value from all columns in that row.
for c = 0 to 8
if c != col
{
len = length[board@row@c]
if len > 1
{
board@row@c.remove[value]
// If it's the last remaining value, eliminate it.
if length[board@row@c] == 1
{
for val = board@row@c
setNoCheck[row, c, val]
}
}
}
// Remove all instances of that value from all rows in that column.
for r = 0 to 8
if r != row
{
len = length[board@r@col]
if len > 1
{
board@r@col.remove[value]
// If it's the last remaining value, eliminate it.
if length[board@r@col] == 1
for val = board@r@col
setNoCheck[r, col, val]
}
}
// Remove all instances of that value from all boxes in that square.
rowstart = (row div 3) * 3
colstart = (col div 3) * 3
for r = rowstart to rowstart + 2
for c = colstart to colstart + 2
if !(r==row and c==col)
{
len = length[board@r@c]
if len > 1
{
board@r@c.remove[value]
// If it's the last remaining value, eliminate it.
if length[board@r@c] == 1
{
for val = board@r@c
setNoCheck[r, c, val]
}
}
}
}
// Solve the board.
solve[verbose=false] :=
{
do
{
dump[]
changed = findSingletons[verbose]
} while (changed)
}
// Find and remove the singletons.
// See http://www.eddaardvark.co.uk/sudokusolver.html#Singletons
findSingletons[verbose] :=
{
if (verbose)
println["Starting findSingletons"]
changed = false
count = new array
// Remove in rows
for r = 0 to 8
{
for c = 0 to 8
count@c = 0
row = board@r
// Remove all instances of that value from all columns in that row.
for c = 0 to 8
{
cell = row@c
if length[cell] > 1 // Exclude already-found values
for v = cell
count@(v-1) = count@(v-1) + 1
}
for n = 0 to 8
if count@n == 1
{
println["Singleton found, row=$r, value=" + (n+1)]
// Find that value
COL1:
for c = 0 to 8
if (board@r@c).contains[n+1] and length[board@r@c] > 1
{
if verbose
println["Found singleton at [$r, $c], changed to " + n+1]
setNoCheck[r,c,n+1]
dump[]
changed = true
break COL1
}
}
}
// Remove in cols
for c = 0 to 8
{
for r = 0 to 8
count@r = 0
// Remove all instances of that value from all columns in that row.
for r = 0 to 8
{
cell = board@r@c
if length[cell] > 1 // Exclude already-found values
for v = cell
count@(v-1) = count@(v-1) + 1
}
for n = 0 to 8
if count@n == 1
{
println["Singleton found, col=$c, value=" + (n+1)]
// Find that value
ROW1:
for r = 0 to 8
if (board@r@c).contains[n+1] and length[board@r@c] > 1
{
if verbose
println["Found singleton at [$r, $c], changed to " + n+1]
setNoCheck[r,c,n+1]
dump[]
changed = true
break ROW1
}
}
}
// Remove in block
for rowblock = 0 to 2
for colblock = 0 to 2
{
rowstart = rowblock * 3
colstart = colblock * 3
for r = 0 to 8
count@r = 0
// Remove all instances of that value from all cells in that
// block
for c = colstart to colstart+2
{
for r = rowstart to rowstart+2
{
cell = board@r@c
if length[cell] > 1 // Exclude already-found values
for v = cell
count@(v-1) = count@(v-1) + 1
}
}
for n = 0 to 8
if count@n == 1
{
println["Singleton found, block=[$rowblock, $colblock] value=" + (n+1)]
// Find that value
BLOCK1:
for c = colstart to colstart+2
{
for r = rowstart to rowstart+2
if (board@r@c).contains[n+1] and length[board@r@c] > 1
{
if verbose
println["Found singleton at [$r, $c], changed to " + n+1]
setNoCheck[r,c,n+1]
dump[]
changed = true
break BLOCK1
}
}
}
}
return changed
}
}
a=["1-8--7462",
"---1--8--",
"9---2---1",
"-----4---",
"6-2-8-3-9",
"---3-----",
"8---5---6",
"--6--2---",
"5136--7-8"]
b = Sudoku.createFromArray[a]
b.dump[]
b.solve[verbose=true]
b.dump[]
c=["----19-4-",
"--48--6--",
"75------2",
"-9-1-2--4",
"-----3---",
"5--4-6-3-",
"8------73",
"--6--84--",
"-1-29----"]
b = Sudoku.createFromArray[c]
b.dump[]
b.solve[false]
b.dump[]
c=["8--91----",
"3-76--9-1",
"-9-------",
"5---3-7-9",
"-34-8-26-",
"9-2-7---4",
"-------5-",
"1-3--24-7",
"----91--3"]
b = Sudoku.createFromArray[c]
b.dump[]
b.solve[false]
b.dump[]
c=["-1-4-63-9",
"----3-85-",
"-------6-",
"-6-5--7-2",
"25-6-7-13",
"4-7--2-9-",
"-7-------",
"-94-5----",
"6-39-4-7-"]
b = Sudoku.createFromArray[c]
b.dump[]
b.solve[false]
b.dump[]
Download or view Sudoku.frink in plain text format
This is a program written in the programming language Frink.
For more information, view the Frink
Documentation or see More Sample Frink Programs.
Alan Eliasen was born 20145 days, 5 hours, 28 minutes ago.