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'

This page was created by F1toHTML