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 19972 days, 12 hours, 37 minutes ago.