No Description
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

sudoku.b93 14KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248
  1. v XX ########### ########### ############################# #############################
  2. C C # 3 17# # # # # # #
  3. PPPPP # 15 9 8# # # # # # #
  4. XXX # 6 # # # # # # #
  5. LLLLLL #1 7 # # # # # # #
  6. PMMMM # 9 2 # # # # ########## # # #
  7. MM MMM # 5 4# # # # ################## # # #
  8. XXX XX # 2 # # # # ################## # # #
  9. #5 6 34 # # # # ####################### # # #
  10. #34 2 # # # # ####################### # # ####### #
  11. ########### ########### # #################### # # ############ #
  12. # #################### # # ############### #
  13. > 492*+11p9:*:9*61p>1-v # ################ # # ################# #
  14. >9+\9/1+p:0\:9%11g+\9/1+p:| # ############ # # ################# #
  15. ^%9:\+*86%+88 g+1/9\+9%9::$#:< # ############ # # ######## ######## #
  16. v1/*93\+*75%*93:\0:-1<g16p021< # ################ # # ################# #
  17. >+p:0\:39*%89*+\39*/#| 1#:+# p# < # #################### # # ################# #
  18. v p030$<>p152p::9%v # ####################### # # ############### #
  19. >9:*>1-:9/32p:9%22p212^vg+1/9\+9< # ####################### # # ############ #
  20. v10 $< >68*-:42pv # ####################### # # ####### #
  21. 4 ^_^#: <v!< # ################## # # #
  22. p @ >1-:9%24p:9/3v^_ v # ########## # # #
  23. >30g9:*-!#^_9:*^ 4$ # ########## # # #
  24. v0p450_v#!-*86 g+g431+g429p< # # # #
  25. > > :#^_$14g#v_015p v # # # #
  26. ^ p410< # # # #
  27. p6 v:p45+1g44 < # # # #
  28. 4>4p9 >1-:44p57*24g3*44g3%+v # # # #
  29. 1 #>|:_v#g++/3g44*3g431+ < ############################# #############################
  30. 0 $ >64g1+64p ^| #
  31. ^ < $<v># #< >025p035p045p9:*:*55p9:*>1-: 9%16p:9/26p916gv
  32. >64g:!#v_1-#^_14g1+14pv#> >42g68*+22g9+3 v ^ < v _v#!g54 $_^#!:<_v#<-*86g+g621+<
  33. v $$<vg43p22g42p211<: v9p03+1g03p+1g2<^ p25g02< v02:+1 g 02<vg65$_ v0p650p640< ^1 <<
  34. >32p54g42p20g5v- >1-:13p"X"57*22g3*13g3%++132g3*13g3v >p11g2 5 g+v! ! >1+:66p57*16g3*66g1-3%v
  35. >>01-::17p27p37p9:*v_$ 9v 21 vg++/3g31*3g231++%3g31*3g22*98p++/< vp210p+g 5 31<5>pv < _v#g++/3-1g66*3g621++<
  36. v94p76/9:p75%9:-1<^:<<: p v _52g89*22g3*13g3%v >25g22p3 5 gv 56 : - >56g1+56p4 v
  37. >2*+57g+167g+g20g- |p: > ^:|:p++/3g31*3g231++< ^ p24g54p 2 3< g4 >9^|+!`g51g66!!g6< p
  38. v*86g+g761+g759<7* >$9>1-:23p"X"57*23g3*42g1-3%++132g3*42g1-3v 5^g66 <> ^5
  39. >-17p57g27 p67g3^* # vg++/3-1g24*3g231++%3-1g24*3g32*98p++/< >6g`!+#^_16g25p26g35p46g45p56g5^
  40. v*98p76/*93:p75%*93:-1< _$ v>^v _52g89*23g3*42g1-3%v v ># ^#<
  41. >57g+167g+g20g-! #v_:^< 2 >:|:p++/3-1g24*3g231++<
  42. v75*750p+g761+g75*980< :: 0v19$<>p"X"57*22g3*42g1-3%+ + 133g3*42g1-3/++v
  43. >167g3/+g 68*-!| g>-:33^vg++/3-1g24*3g331++% 3 -1g24*3g22*98p <
  44. ^+/3g759<v61+/ 3g759*86< 1^1 < v_52g89*22g3*42g1-3%v
  45. >g+167g+p^>7g3/+p30g1-30p^ - |:< p++/3-1g24*3g331++<
  46. vp51g71p+g731+g72+*2940p02 < >$9>1-::3%23p3/33p"X"57 * 22g3/3*23g+3*42g1-3%++132g3/3*33g+3*42gv
  47. ^ ># #<v > ^ v># #<^ vg++/3-1g24*3+g33* 3 /3g231++%3-1g24*3+g32*3/3g22*98p++/3-1 <
  48. ^ $_^#!:g21$< v :_52g89*22g3/3*23g+ 3 *42g1-3%v
  49. ^># #<v^ _^#: p++/3-1g24*3+g33* 3 /3g231++<
  50. ^># #< ^
  51. #$watch[2,0]:int = recursionLevel
  52. #$watch[3,0]:int = solvedCells
  53. #$watch[1,2]:int = SetValueAndHints :: returnAddr
  54. #$watch[2,2]:int = SetValueAndHints :: cx
  55. #$watch[3,2]:int = SetValueAndHints :: cy
  56. #$watch[4,2]:int = SetValueAndHints :: value
  57. #$watch[5,2]:int = SetValueAndHints :: recDepth
  58. #$watch[1,3]:int = it_v
  59. #$watch[2,3]:int = it_x
  60. #$watch[3,3]:int = it_y
  61. #$watch[1,4]:int = Solve :: changes
  62. #$watch[2,4]:int = Solve :: x
  63. #$watch[3,4]:int = Solve :: y
  64. #$watch[4,4]:int = Solve :: v
  65. #$watch[5,4]:int = Solve :: rv
  66. #$watch[6,4]:int = Solve :: cc
  67. #$watch[1,5]:int = RecursionStepDown :: lo
  68. #$watch[2,5]:int = RecursionStepDown :: bx
  69. #$watch[3,5]:int = RecursionStepDown :: by
  70. #$watch[4,5]:int = RecursionStepDown :: bv
  71. #$watch[5,5]:int = RecursionStepDown :: bvc
  72. #$watch[1,6]:int = RecursionStepDown :: fbx
  73. #$watch[2,6]:int = RecursionStepDown :: fby
  74. #$watch[4,6]:int = RecursionStepDown :: v
  75. #$watch[5,6]:int = RecursionStepDown :: vc
  76. #$watch[6,6]:int = RecursionStepDown :: tv
  77. #$watch[1,7]:int = RecursionStepUp :: latterstepV
  78. #$watch[2,7]:int = RecursionStepUp :: latterstepX
  79. #$watch[3,7]:int = RecursionStepUp :: latterstepY
  80. #$watch[5,7]:int = RecursionStepUp :: it_x
  81. #$watch[6,7]:int = RecursionStepUp :: it_y
  82. ARRAY [09,01] (W= 9;H= 9) grid // ASCII
  83. ARRAY [22,01] (W= 9;H= 9) rlatter // decimal
  84. ARRAY [35,01] (W=27;H=27) pspace // bool (0d | "X")
  85. ARRAY [72,01] (W=27;H=27) rstack // decimal
  86. [1,1] CONST X-Start-rlatter 22 => 492*+
  87. [2,1] CONST
  88. [3,1] CONST
  89. [4,1] CONST
  90. [5,1] CONST
  91. [6,1] CONST Big array size 27*27 = 729 => 9::**
  92. // X-Start-rlatter 22 => 492*+
  93. // Big array width 27 => 39*
  94. // X-Start-pspace 35 => 57*
  95. // ASCII '0' "0" = 48 => 68*
  96. // X-Start-rstack 72 => 89*
  97. // Small array size 9*9 = 81 => 9:*
  98. // Big number 6561 => 9:*:*
  99. ---------------------------------------
  100. Introduction
  101. ============
  102. First we need a data structure for the current state, we simply take a `9x9` array
  103. (a sudoku puzzle contains nine `areas` with nine `fields` each = 9x9 fields in total).
  104. A zero in a field means `unkown` and the numbers one to nine are valid values.
  105. Because I wanted the program too look a little bit aesthetically pleasing
  106. I used ASCII-numbers instead of raw binary values ;).
  107. This array is from now on called `grid`.
  108. Next we need a place to remember which values are possible for a specific array.
  109. Therefore we use a 3x3 array for each field which fields represent the
  110. nine possible numbers (`1..9`).
  111. This data is structured into a `27x27` field (`= (9*3)x(9*3)`).
  112. This array is from now on called `pspace`
  113. Set Up
  114. ======
  115. Initially we take the known values from our input and write them to the `grid` array.
  116. For each value we also have to update the `pspace`.
  117. If we set a value in the grid to `v` at position `[x|y]` we have to
  118. - set the `pspace[dx, dy, v]` of all fields `dx|dy` in the same area to true
  119. - set the `pspace[dx, dy, v]` of all fields `dx|dy` in the same row to true
  120. - set the `pspace[dx, dy, v]` of all fields `dx|dy` in the same column to true
  121. We can calculate the position in the `pspace` are like this:
  122. ~~~
  123. px = (x*3) + ((v - 1)%3)
  124. py = (y*3) + ((v - 1)/3)
  125. ~~~
  126. Solving simple puzzles
  127. ======================
  128. After we initialized the array we scan all fields and search
  129. for pspace configurations where all numbers are set to `1` except one.
  130. For these it is unambiguous which value it has (the one where `pspace== `)
  131. Then we set this value in the `grid` array (and - again - update the `pspace`).
  132. This step is repeated until the whole puzzle is solved.
  133. (We need a isSolved function for this, but it only needs to check
  134. for zeroes in the `grid` array).
  135. Solving the rest
  136. ================
  137. The described approach works great for the first puzzle, but as soon
  138. as we try the second one we stumble upon a problem.
  139. There a situation where not a single field has a obvious solution and we
  140. need to "guess" a value to continue. (And then backtrack if the guess
  141. was wrong and try the next possibility).
  142. For this we introduce two new arrays into our memory model `rstack[27,27]` and `rlatter[9,9]`.
  143. And we keep track of a global value that we call `recursionDepth` (initially `1`).
  144. Every time we set a value in our `pspace` we write into
  145. the corresponding `rstack` field our current `recursionDepth`.
  146. Now as soon as we encounter a dead end (all fields are either solved or have multiple possible solutions)
  147. we go one step down.
  148. First we increase the `recursionDepth` by 1.
  149. Then we take the easiest field (field with the least possible values) and set it to the lowest possible value.
  150. We also set the corresponding field in `rlatter` to the current `recursionDepth`.
  151. Now we continue with our algorithm as before until one of three things happen:
  152. 1. We solve all fields. Then we found the solution and our program terminates.
  153. 2. We have again the situation with no unambiguous fields, then we do the whole thing again and increase the `recursionDepth` again.
  154. 3. We end up with a field which `pspace` contains only ones (meaning there is no possible value for this field).
  155. In case 3 it is obvious that we must have guessed wrong in the past.
  156. So first we undo the last recursion step.
  157. We iterate through the whole `rstack` and everywhere where the value equals our current `recursionDepth`
  158. we set the corr corresponding `pspace` value to zero.
  159. If the value in `grid` at this position is not zero we set it to zero
  160. (because we must have set it in this recursion level and now we can't be sure if its correct).
  161. Then we decrease the `recursionDepth` by one again.
  162. Before we reseted all the values we looked into our `rlatter` to get the grid position that
  163. was guessed when we entered this `recursionDepth`
  164. (This is simply done by searching the field with the value `recursionDepth`).
  165. Now we "guess" the next possible value for this field and increase the recursion
  166. depth once again (and continue with our normal operations).
  167. If we can't find another value for this field (means we tried all available and all where wrong)
  168. we simply go one step further up (decrease the `recursionDepth` again, complete with undoing all changes etc)
  169. and take the next value of this guess.
  170. This algorithms runs until we either find a solution or there is no solution
  171. (in this case we would after a while try to undo the `recursionDepth` 1 and go into `recursionDepth` ).
  172. Design decisions
  173. ================
  174. This algorithm is definitely not the best in a normal C-like language but it has a its pros in befunge.
  175. First we have realized recursion-like behavior without a stack or an data structure with unknown size
  176. (which would happen if we simply wrote the "stack" to our befunge-grid).
  177. It is true that we could possibly be used the normal befunge-stack for our recursion-stack.
  178. But we do enough stuff already on the stack that this would result in a much more complex program
  179. (and at times a really big stack).
  180. My solution with an additional grid (`rstack`) is imho quite elegant and has a fixed size from the beginning on.
  181. I didn't optimize this program as much as possible. Not only because its quite a big program but also because it
  182. doesn't need to be terribly fast and because I wanted to keep the interesting
  183. look with thee four array fields while solving.
  184. In the end this is not my fastest solution but a complete sudoku solver in befunge is in my opinion quite cool.
  185. As with most bigger befunge programs I made a reference Implementation in C# (with LinqPad),
  186. if someone wants to better understand this algorithm, perhaps also look at this code :D
  187. Befunge Modules
  188. ===============
  189. In my reference C# implementation I have a few methods that get called multiple times from different origins.
  190. But (through carefully writing the code) there is never a case where the same method is multiple times on the call stack
  191. (so the program is not recursive, even though the algorithm is).
  192. I didn't want to duplicate code, especially not some of the bigger methods so I used a special cell to remember the "return value".
  193. After the method has finished it then can decide on its own where the PC has to flow to resume the program.
  194. One example is the method `SetValueAndHints`. This method can get called from three different positions:
  195. - In the initialization phase
  196. - When `RecursionStepDown` fails and we discard the current guess
  197. - When a cell contains invalid data and we discard the current guess
  198. The return address is part of the "parameter-package" that gets written every time `SetValueAndHints` is called
  199. (The package contains `returnAddr`, `cx`, `cy`, `value`, `recDepth`).
  200. Because *(see above)* the method is never two times on our theoretical "call stack" we don't have problems with someone overriding
  201. values there while they are still used.
  202. For the method `RecursionStepDown` we got lucky. Even though the method is called from two different positions we could rearrange
  203. our algorithm in a way that the return address of both calls is the same,
  204. that means we don't need a return address (but still a parameter package).
  205. The same is true for `RecursionStepUp`, it is called from two sources but both time it returns into a call of `RecursionStepDown`.