Home More Samples
```///////////////////////////////////////////////////////////////////////////////
//
// SudokuGUI.f1
//
// SUDOKU puzzle solver with a Graphical User Interface.
//
// The puzzle was invented in Basel, Switzerland, by 18th century matematician
// Leonhard Euler. Euler called his puzzle "Magic Squares", it became
// "Sudoku" ("single number" in Japanese) in the 1980s. The puzzle comes in
// several variants, the most common being a square grid nine by nine, consisting
// of nine sub-grids 3x3. This variant is often referred to as Sudoku 3x3.
// There are numerous Sudoku web sites dealing with history, solving strategies
// and posting new puzzles. Puzzles are often rated by their difficulty.
//
// The rules: Fill the grid with numbers so that each column, each row
// and each each tree by three grid of nine squares contains the numbers
// one to nine. No column, row or grid can have two of the same numbers.
//
// Solving:
// The code in the predicate SudokuSolve3x3 will solve any Sudoku problem. It is
// an ideal problem for declarative programming: all the code does is transcribe
// the rules above in the syntax of the F1 language.
// Though the actual solving is done by the predicate SudokuSolve3x3, all input/output
// routines are handled by an external module SudokuExt.dll. All in all we need
// five external routines to handle this programs' needs from inputing of
// the user values to displaying the found solutions.
//
// Note the usage of the routines RtlGetCutPoint / RtlSetCutPoint. These routines
// are needed in case the user does not want all solutions. By using these routines
// we are able to prematurely terminate the predicate SudokuSolve3x3, explicitly
// cutting off the predicate backtracking branches.
//
// To execute the program, issue the query
//
//      SudokuGUI
//
// Final note: The code will find all solutions, therefore can be easily used
// to generate new Sudoku puzzles: simply start with any partially filled grid,
// generate all solution, and keep filling the grid with more numbers until
// the puzzle has a single solution.
//
///////////////////////////////////////////////////////////////////////////////

local SUDOKUTYPE = [0..80]->I[1..9]
local ATYPE = [0..8]->>I[1..9]

subr SudokuGUI() iff
SudokuCreateWindow('F1 3x3 Sudoku Solver',h) & SudokuGUISolve(h)

local subr SudokuGUISolve(h:<I) iff
SudokuGetUserValues(h,arr) &
all x in l
RtlGetCutPoint(cp) &
SudokuSolve3x3(x,arr) & ShowResult(x,h) &
if ~SudokuQueryNext() then
RtlSetCutPoint(cp)
end
end & SudokuDone() &
SudokuGUISolve(h)

local pred SudokuSolve3x3(s::SUDOKUTYPE , a:<[0..80]->[0..9]) iff
Assign(s,a,0) &

DiffCols(s,0) & DiffCols(s,1) & DiffCols(s,2) &
DiffCols(s,3) & DiffCols(s,4) & DiffCols(s,5) &
DiffCols(s,6) & DiffCols(s,7) & DiffCols(s,8) &

DiffRows(s,0) & DiffRows(s,1) & DiffRows(s,2) &
DiffRows(s,3) & DiffRows(s,4) & DiffRows(s,5) &
DiffRows(s,6) & DiffRows(s,7) & DiffRows(s,8) &

DiffSubGrid(s,0,0) & DiffSubGrid(s,0,3)  & DiffSubGrid(s,0,6) &
DiffSubGrid(s,3,0) & DiffSubGrid(s,3,3)  & DiffSubGrid(s,3,6) &
DiffSubGrid(s,6,0) & DiffSubGrid(s,6,3)  & DiffSubGrid(s,6,6)

local pred DiffSubGrid(s::SUDOKUTYPE, row:<I, col:<I) iff
sg::ATYPE & sg = [
s(row*9+col),s(row*9+col+1),s(row*9+col+2),
s((row+1)*9+col),s((row+1)*9+col+1),s((row+1)*9+col+2),
s((row+2)*9+col),s((row+2)*9+col+1),s((row+2)*9+col+2)]

local pred DiffCols(s::SUDOKUTYPE, col:<I) iff
sg::ATYPE & sg = [
s(col), s(col+9), s(col+2*9), s(col+3*9),
s(col+4*9),s(col+5*9),s(col+6*9), s(col+7*9),
s(col+8*9)]

local pred DiffRows(s::SUDOKUTYPE, row:<I) iff
sg::ATYPE & sg = [
s(row*9), s(row*9+1),s(row*9+2), s(row*9+3),
s(row*9+4),s(row*9+5),s(row*9+6), s(row*9+7),
s(row*9+8)]

local proc ShowResult(s:<SUDOKUTYPE, h:<I) iff
SudokuShowValues(h,s:([0..80]->I))

local pred Assign(s::SUDOKUTYPE, a:<[0..80]->[0..9],col:<I) iff
if col < Len(s) then
if a(col) <> 0 then
s(col) = a(col)
end & Assign(s,a,col+1)
end

///////////////////////////////////////////////////////////////////////////////
//
// External routines used by this program.
//
///////////////////////////////////////////////////////////////////////////////

// Initialize the external code
local subr SudokuCreateWindow(title :<S,w:>I) iff
external 'SudokuExt':'SudokuCreateWindow'

// Query the external code for some initial Sudoku values
local subr SudokuGetUserValues(w:<I,a:>[0..80]->I[0..9]) iff
external 'SudokuExt':'SudokuGetUserValues'

// Present the external code with one Sudoku solution
local proc SudokuShowValues(w:<I,a:<[0..80]->I) iff
external 'SudokuExt':'SudokuShowValues'

// Notify the external code we are finished (there will be no more solutions)
local proc SudokuDone() iff
external 'SudokuExt':'SudokuDone'

// Query the external code if another solution desired
local proc SudokuQueryNext() iff
external 'SudokuExt':'SudokuQueryNext'

```