|
![]() |
||||||||||||||
Examples TutorialSudokuSudoku 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"
|
|
||||||||||||||
© 2006 Saša Malkov | |||||||||||||||