[SPOILER] Euler problem #96
Marcel Hendrix
The reading of the problems could be done VASTLY simpler.
FORTH> in euler96
Creating --- Sudoku solver Version 1.15 ---
Creating --- Sudoku solver Version 1.00 ---
Euler96 -- Solve 50 Sudoku puzzles and find the sum of the 3-digit
-- numbers found in the top left corner of each solution grid
ok
FORTH> euler96
The sum of the 3-digit numbers found in the top left corner of each solution grid is 2x,xxx.
0.067 seconds elapsed. ok
-marcel
-- euler96.frt -----------------------------------------------------------------
INCLUDE ../games/sudoku.frt
(*
Su Doku (Japanese meaning number place) is the name given to a popular
puzzle concept. Its origin is unclear, but credit must be attributed to
Leonhard Euler who invented a similar, and much more difficult, puzzle
idea called Latin Squares. The objective of Su Doku puzzles, however, is
to replace the blanks (or zeros) in a 9 by 9 grid in such that each row,
column, and 3 by 3 box contains each of the digits 1 to 9. Below is an
example of a typical starting puzzle grid and its solution grid.
0 0 3 0 2 0 6 0 0 4 8 3 9 2 1 6 5 7
9 0 0 3 0 5 0 0 1 9 6 7 3 4 5 8 2 1
0 0 1 8 0 6 4 0 0 2 5 1 8 7 6 4 9 3
0 0 8 1 0 2 9 0 0 5 4 8 1 3 2 9 7 6
7 0 0 0 0 0 0 0 8 7 2 9 5 6 4 1 3 8
0 0 6 7 0 8 2 0 0 1 3 6 7 9 8 2 4 5
0 0 2 6 0 9 5 0 0 3 7 2 6 8 9 5 1 4
8 0 0 2 0 3 0 0 9 8 1 4 2 5 3 7 6 9
0 0 5 0 1 0 3 0 0 6 9 5 4 1 7 3 8 2
A well constructed Su Doku puzzle has a unique solution and can be
solved by logic, although it may be necessary to employ "guess and
test" methods in order to eliminate options (there is much contested
opinion over this). The complexity of the search determines the
difficulty of the puzzle; the example above is considered easy
because it can be solved by straight forward direct deduction.
The 6K text file, sudoku.txt, contains fifty different Su Doku puzzles
ranging in difficulty, but all with unique solutions (the first puzzle
in the file is the example above).
By solving all fifty puzzles find the sum of the 3-digit numbers found
in the top left corner of each solution grid; for example, 483 is the
3-digit number found in the top left corner of the solution grid above.
Example (CR+LF delimited, no final delimiter):
Grid 01
003020600
900305001
001806400
008102900
700000008
006708200
002609500
800203009
005010300
Grid 02
200080300
060070084
030500209
000105408
000000000
402706000
301007040
720040060
004010003
...
*)
\ the Euler Sudoku file
CREATE sname #10 CHARS ALLOT
CREATE temp #128 CHARS ALLOT
: READ-ES ( u -- num )
0 0 LOCALS| old-do handle su |
S" sudoku.txt" R/W BIN OPEN-FILE THROW TO handle
( skip unwanted sudoku's )
su #10 * 0 ?DO
temp #12 handle READ-LINE THROW NIP
0= IF CR ." ==EOF==" UNLOOP EXIT
ENDIF
LOOP
( read name)
sname CHAR+ #12 handle READ-LINE THROW DROP sname C!
( read data )
9 0 DO temp I 9 * + #12 handle READ-LINE THROW DROP
9 <> ABORT" READ-ES :: sudoku line size error"
LOOP
handle CLOSE-FILE THROW
temp #81 BOUNDS DO I C@ '0' - I C! LOOP
sname COUNT temp #81 + PACK DROP
temp TO original startsolving 0= ABORT" READ-ES :: couldn't solve SUDOKU"
0 sudokugrid 3 BOUNDS DO #10 * I C@ + LOOP ;
: .TOPSUM ( -- ) 0 #50 0 DO I READ-ES + LOOP . '.' EMIT ;
: Euler96 ( -- )
CR ." The sum of the 3-digit numbers found in the top left corner of each solution grid is "
.TOPSUM ;
: .ABOUT CR ." Euler96 -- Solve 50 Sudoku puzzles and find the sum of the 3-digit "
CR ." -- numbers found in the top left corner of each solution grid" ;
.ABOUT