Su Doku
Problem 096: Su Doku
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
9 0 0 3 0 5 0 0 1
0 0 1 8 0 6 4 0 0
0 0 8 1 0 2 9 0 0
7 0 0 0 0 0 0 0 8
0 0 6 7 0 8 2 0 0
0 0 2 6 0 9 5 0 0
8 0 0 2 0 3 0 0 9
0 0 5 0 1 0 3 0 04 8 3 9 2 1 6 5 7
9 6 7 3 4 5 8 2 1
2 5 1 8 7 6 4 9 3
5 4 8 1 3 2 9 7 6
7 2 9 5 6 4 1 3 8
1 3 6 7 9 8 2 4 5
3 7 2 6 8 9 5 1 4
8 1 4 2 5 3 7 6 9
6 9 5 4 1 7 3 8 2A 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 (right click and 'Save Link/Target As...'), 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.
Solution:
C C ########### # # # # # # 900305001524010000008400000080960010000907000009000800800701040049070250050123400010000000
PPPPP ########### # # # # # # 001806400000000070420800000400000057900208005640020000040020030000405000030000160000706500
XXX ########### # # # # # # 008102900050008102030000095008000471004806500000001008374000900600317004908000000000800090
LLLLLL ########### # # # # # # 700000008000000000060902010000603000607000208208000501000030000007000800070000090020904060
PMMMM ########### # # # ########## # # # 006708200402700090510000060259000800003102900700500000005000321100826009000000205040002000
MM MMM ########### # # # ################## # # # 002609500060000000000003049740000005800605007000090084010060050000702000091000050001607000
0XXX XX ########### # # # ################## # # # 800203009000030945000007200020018060000309000003000600050802006075040190007439020000000030
7 ########### # # # ####################### # # # 005010300000071006001298000005470329030020050060003002080000000003090600400007000300005702
7 ########### # # # ####################### # # ####### # 200080300043080250062340750050807020005000006007256400000000085005080700380000000000700800
* ########### ###########v<# #################### # # ############ # 060070084600000000100005600600010090070009020400000005000210009700204005000400785006000031
> #v #<v# #################### # # ############### # 030500209000001094570000040702540006000500107010030060960080100320000084009020300040002000
> 492*+11p9:*:9*61p>1-v## ################ # # ################# # 000105408900004070000094800070020301804150000000508000500800016060105040060090000024070000
>9+\9/1+p:0\:9%11g+\9/1+p:| # ############ # # ################# # 000000000000608000400000006504000908000803000008060200000000000008000500800302009010030080
^%9:\+*86%+88 g+1/9\+9%9::$#:< # ############ # # ######## ######## # 402706000010200003005830000103080070000092805000107000890006007070803010000040070000060290
v1/*93\+*75%*93:\0:-1<g16p021< # ################ # # ################# # 301007040820500000030000091900076205907006000030070090009070052450000091001070500000800070
>+p:0\:39*%89*+\39*/#| 1#:+# p# < # #################### # # ################# # 720040060000000005006400007060090003030400010200000004300054000600508007495006000860000500
v p030$<>p152p::9%v # ####################### # # ############### # 004010003034090710059083260080103040200000600006312700480000000003010600000000092002006000
>9:*>1-:9/32p:9%22p212^vg+1/9\+9< # ####################### # # ############ # 000000907480006902300000000080005000040000050000000000608070502000900800000158000001007090
v10 $< > v>68*-:42pv # ####################### # # ####### # 000420180002008001005009000000003457001943600079050180050608070128006400002060800590080001
4 ^_^#: # <v!< # ################## # # # 000705026900370060200504000000070809009000300800000007002000300070800060030000040030000080
p >1-:9%24p:9/3v^_ v # ########## # # # 100904000840010200020000700060400903600050002007306800500090006800430007027030510000005800
>30g9:*-!#^_9:*^ > #4 v# ########## # # # 050000040003704100160000058007010500103000506450708096040302050500000009000000000050060020
v0p450_v#!-*86 g+g431+g429p<$ ## # # #v <000507009001060049704310600408007020800020007003502700800050003600079008046080790004100000
> > :#^_$14g#v_015p v # # # # v _$:1+|920108000020085007000890100901020000005000200700000005005000200090004010050000080080000030
^ p410< ## # # #1>+\g13g9 %9+13g9/1+p:^ v<034059000700900600000067080842300000002436700016030420010704090003600284004070100100020079
p6 v:p45+1g44 < > ^# # # #-^+**882* 9/5g06%9g31+*9< $ 507000000609200018000005437000100080030000040000000000409060701001007000000325000020700400
4>4p9 >1-:44p57*24g3*44g3%+v # # # # >:60p99*>1-::13p9/60g5%^ . 030050040000900002630000000003502900004000000030000080050010040000080000010500200000003017
1 #>|:_v#g++/3g44*3g431+ < ############################# ############################# ^ < \++-*86<@ 008010500050123400000500008000040000000030002009000500107000602270000054900001000015009008
0 $ >64g1+64p ^|^ #># #<:77*-!#^_\91g68*-55+*55v 460000012030000160005674000106000305390700080007509200000905000095000810002008030060000000
^ < $<v># #< >025p035p045p9:*:*55p9:*>1-: 9%16p:9/26p916gvv+-*86g1+< 070502080908000000000020000900251008400009001700105008208030501009806400500030007100007000
>64g:!#v_1-#^_14g1+14pv#> >42g68*+22g9+3 v ^ < v _v#!g54 $_^#!:<_v#<-*86g+g621+<>55+*56+1g^ 000603000070000090003401020070408030209801307020090030040070020020403060008000500009000200
v $$<vg43p22g42p211<: v9p03+1g03p+1g2<^ p25g02< v02:+1 g 02<vg65$_ v0p650p640< ^1 << 040109030000000205000000345800763001600200008900402001901080406006905100600080004000500004
>32p54g42p20g5v- >1-:13p"X"57*22g3*13g3%++132g3*13g3v >p11g2 5 g+v! ! >1+:66p57*16g3*66g1-3%v 250000098091000050000007004308000104010008053004207100000401000017000620040100700000000020
>>01-::17p27p37p9:*v_$ 9v 21 vg++/3g31*3g231++%3g31*3g22*98p++/< vp210p+g 5 31<5>pv < _v#g++/3-1g66*3g621++< 001020600007439020080300902000020000900040000002000800304000709460000038000700006500600340
v94p76/9:p75%9:-1<^:<<: p v _52g89*22g3*13g3%v >25g22p3 5 gv 56 : - >56g1+56p4 v 080060020400007000947100080005104800000000800070000090020060010000090000003004050340200000
>2*+57g+167g+g20g- |p: > ^:|:p++/3g31*3g231++< ^ p24g54p 2 3< g4 >9^|+!`g51g66!!g6< p 020810740001900003000020040000000000360020089200170603053000790000602000080000040300200000
v*86g+g761+g759<7* >$9>1-:23p"X"57*23g3*42g1-3%++132g3*42g1-3v 5^g66 <> ^5 700003100900700160008035000009805100000361000050000100009753400400050001000469000000107000
>-17p57g27 p67g3^* # vg++/3-1g24*3g231++%3-1g24*3g32*98p++/< >6g`!+#^_16g25p26g35p46g45p56g5^ 090002805030005007000070602051907420000000000000006079100000002085010620400000007706030500
v*98p76/*93:p75%*93:-1< _$ v>^v _52g89*23g3*42g1-3%v v ># ^#< 009040087050000009031046970290401065803000602000040700090080010038206710005904600070009080
>57g+167g+g20g-! #v_:^< 2 >:|:p++/3-1g24*3g231++< 400208003004302600200000000000000000400603007000801000000907000000000000070608030900020004
v75*750p+g761+g75*980< :: 0v19$<>p"X"57*22g3*42g1-3%+ + 133g3*42g1-3/++v 160030200200000070000501203140508093607000108009050000080030070019407350008502100010800050
>167g3/+g 68*-!| g>-:33^vg++/3-1g24*3g331++% 3 -1g24*3g22*98p < 302700060600100030049000730026709580000000000310400000500000003026040530900000005009040301
^+/3g759<v61+/ 3g759*86< 1^1 < v_52g89*22g3*42g1-3%v 005600008042007006000000010005103600000418000005000060007641200900020007000781000000702000
>g+167g+p^>7g3/+p30g1-30p^ - |:< p++/3-1g24*3g331++< 076051090500006800800004000000000000970030014906037002061000940000809000060000010000008006
vp51g71p+g731+g72+*2940p02 < >$9>1-::3%23p3/33p"X"57 * 22g3/3*23g+3*42g1-3%++132g3/3*33g+3*42gv
^ ># #<v > ^ v># #<^ vg++/3-1g24*3+g33* 3 /3g231++%3-1g24*3+g32*3/3g22*98p++/3-1 <
^ $_^#!:g21$< v :_52g89*22g3/3*23g+ 3 *42g1-3%v
^># #<v^ _^#: p++/3-1g24*3+g33* 3 /3g231++<
^># #< ^
Explanation:
This problem boils down to implementing a sudoku solver. So thats what I did (initially as a stand-alone project). And then I wrote a program around that inputs the 5 puzzles into the solver and calculates the result.
This means in this post I'm trying to describe how to build a sudoku solver in befunge.
Because all the logic is practically a stand-alone sudoku solver, I simply wrote one. You can read about the development and a few of my design decisions in this blogpost here. The rest was looping 50 times through the solver code and adding the results together.
Really all the interesting stuff is written in the blogpost about the sudoku solver, go read it!
| Interpreter steps: | 583 893 708 |
| Execution time (BefunExec): | 1min 30s (6.42 MHz) |
| Program size: | 218 x 50 |
| Solution: | 24702 |
| Solved at: | 2016-10-25 |