Wafl Home

Examples Tutorial

Sudoku

Sudoku is a logical game where one should replace empty positions in a 9x9 square by digits 1-9 in such way that no horizontal or vertical line or 3x3 square contains repeated digits.

Here we present a Wafl solution for Sudoku. A problem is represented by a string of 81 characters, representing consecutive positions. Empty positions are represented by character x.

Source code:

sudoku( 
    '5x3718x2x'
    'xx652xxxx'
    '7x1xxxxx5'
    'x3x9x2x6x'
    '9xxxxxxx7'
    'x8x4x7x1x'
    '4xxxxx1x8'
    'xxxx416xx'
    'x1x3957x2'
)
    
where{
    //  Sudoku solver
    sudoku( problem ) =
        problem
            ->firstSolution()
            ->displaySolution( problem );

    displaySolution( solution, problem ) =
        "Sudoku problem:\n" + display9x9( problem )
        + "\n\n"
        + if solution='' then 'No solution exists!'
          else "Sudoku solution:\n" + display9x9( solution );

    display9x9( state ) = 
        state->strLeft(9) 
        + if state->strLen() > 9 
            then '\n' 
                + display9x9(state->strRight(state->strLen()-9))
            else '';

    //  Find first solution
    firstSolution( problem ) =
        if stateIsConsistent( problem ) 
            then firstSolutionWithAllCandidates(
                    problem,
                    ['1','2','3','4','5','6','7','8','9']
                    )
            else ''
    where{
        firstSolutionWithAllCandidates( problem, allcandidates ) =
            firstSolutionFromPos( 
                problem, problem->strPos('x'), 
                allcandidates 
                );

        //  If the first unknown symbol is at xpos,
        //  try to find a solution by replacing it with a digit
        //  from the list of all candidates
        firstSolutionFromPos( problem, xpos, allcandidates ) = 
            if xpos<0 
                then problem
                else findSolutionUsingFilteredCandidates(
                    problem,
                    xpos,
                    possibleCandidates( 
                        problem, xpos, 
                        allcandidates 
                        ),
                    allcandidates
                    )
        where{
            // Find possible candidates for the problem at xpos,
            // by elliminating digits present in enclosing lines 
            // and square
            possibleCandidates( problem, xpos, allcandidates ) =
                allcandidates
                ->filter(
                            (
                            enclosingHorLine( problem, xpos )
                            + enclosingVerLine( problem, xpos )
                            + enclosingSquare( problem, xpos )
                            )
                            ->notContains(_)
                        );

            notContains(s,c) = s->strPos(c)<0;
            };
                
        //  Try to find a solution by replacing symbol at xpos 
        //  by a digit from candidates
        //  and, if successfull, go further
        findSolutionUsingFilteredCandidates( 
            problem, xpos, 
            candidates, allcandidates 
            ) =
            if candidates->empty() 
                then ''
                else firstSolutionWithAllCandidates(
                        problem->replaceXByDigit( 
                            xpos, 
                            candidates->hd() 
                            ),
                        allcandidates
                        )
                    ->backTrackIfNotSolution(
                        problem, xpos, 
                        candidates,
                        allcandidates
                        )
        where{
            replaceXByDigit( state, xpos, digit ) =
                state->strLeft(xpos) 
                + digit 
                + state->strRight(80-xpos);
            };
                
        //  If it is a solution, then it's ok, 
        //  but if it is not, then make a step back
        backTrackIfNotSolution( 
            solution, 
            back, xpos, 
            candidates, allcandidates 
            ) =
            if solution != '' 
                then solution
                else findSolutionUsingFilteredCandidates( 
                        back, xpos, 
                        candidates->tl(), 
                        allcandidates 
                        );
    };

    //  Check if position is consistent
    stateIsConsistent( state ) =
        [0,9,18,27,36,45,54,63,72]
            ->map(horLine(state,_))
            ->forall( testPart )
        and
        [0,1,2,3,4,5,6,7,8]
            ->map(verLine(state,_))
            ->forall( testPart )
        and
        [0,3,6,27,30,33,54,57,60]
            ->map(square(state,_))
            ->forall( testPart )
    where{
        //  check if 9 digit sequence is consistent
        testPart(state) =
            state->strLen()<=1
            or check(
                    state->strLeft(1), 
                    state->strRight(state->strLen()-1)
                    );
            
        check(ch,state) =
            ( ch='x' or state->strPos(ch)<0 )
            and testPart(state);
    };

    // Functions for extraction of parts of the state:
    // - horizontal line starting from pos
    horLine(state,pos) =
        state->subStr(pos,9);
    // - horizontal line enclosing the given pos
    enclosingHorLine(state,pos) =
        horLine(state,pos-pos%9);
    // - vertical line starting from pos
    verLine(state,pos) =
        state->subStr(pos,1) 
        + state->subStr(9 + pos,1)
        + state->subStr(18 + pos,1)
        + state->subStr(27 + pos,1)
        + state->subStr(36 + pos,1)
        + state->subStr(45 + pos,1)
        + state->subStr(54 + pos,1)
        + state->subStr(63 + pos,1)
        + state->subStr(72 + pos,1);
    // - vertical line enclosing the given pos
    enclosingVerLine(state,pos) =
        verLine(state,pos%9);
    // - square from pos
    square(state,pos) = 
        state->subStr(pos,3) 
        + state->subStr(pos+9,3) 
        + state->subStr(pos+18,3);
    // - square enclosing the given pos
    enclosingSquare(state,pos) =
        square(state, pos - pos % 27 + pos % 9 - pos % 3);
}

Result:

"Sudoku problem:
5x3718x2x
xx652xxxx
7x1xxxxx5
x3x9x2x6x
9xxxxxxx7
x8x4x7x1x
4xxxxx1x8
xxxx416xx
x1x3957x2

Sudoku solution:
593718426
846529371
721634895
137982564
964153287
285467913
459276138
372841659
618395742"

 

Table of Contents

Let's Start

Program Structure

Primitive Data Types

List

Tuple

Record

HTML

Command Line Interpreter

Using Web Servers

Syntax

Examples

Tips

The most of examples evaluates with both command line and Web server Wafl interpreters. If any example is based on specific features of an interpreter, it is explicitly annotated.