0votos

Tur cerrado del caballo (closed Knight's tour) en Clojure

por AverageUser hace 1 año

Closed knight's tour en Clojure. Funciona con tablero de NxN donde 5<N<19 y N es par. pero quien sabe, si su computadora es rápida, deberían probar N = 20

Dado un tablero de Ajedrez NxN (N >= 6 ) y una posición inicial, recorrer cada casilla del tablero (NxN) sin pasar por ninguna 2 veces .Por ultimo , el caballo debe terminar su recorrido en cualquier casilla que se encuentre exactamente a un movimiento legal de caballo de donde comenzó.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
(ns ckt.core 
  (:gen-class)) 
 
(defn isin? 
  "Returns true if x is an element of list, 
   and nil if is not." 
  [list x] 
  (some #(= x %) list)) 
 
(defn board-f 
  "board-f(3) = [[0 0 0] [0 0 0] [0 0 0]]. 
  Returns a vector of length size with vectors 
  of length size inside." 
  [size] 
  (vec (repeat size (vec (repeat size 0))))) 
 
(defn options 
  "Returns every possible options that a knight 
  have in certain position of certain board." 
  [board [y x]] 
  (for [[v h] [[ 1  2] [ 1 -2] [-1  2] [-1 -2] 
               [ 2  1] [ 2 -1] [-2  1] [-2 -1]] 
        :let [p [(+ v y) (+ h x)]] 
        :when (= 0 (get-in board p))] 
    p)) 
 
(defn best->worst 
  "Using Warnsdorff's Rule determines the priority 
  of the several knigt-moves options." 
  [board pos] 
  (let [op (options board pos) 
        sop (map #(vector (count (options board %)) %) op)] 
    (vec (map #(last %)(sort sop))))) 
 
(declare check-options)                                      ;; Declare the not yet defined check-options function. 
 
(defn jumps 
  " c = counter, n = board size, pos = current position, ipos = initial position. 
  If every square of the board has being visitated once, and the final square 
  it's at one knight-move from the start, returns board. If c is equal to -1 then 
  returns nil. If none of that is true, then calls check-options." 
  [board pos c n ipos] 
  (cond (and (>= c (* n n)) (isin? (options (board-f n) pos) ipos)) board 
        (= c -1) nil 
        :else (let [op (best->worst board pos)] 
                (check-options board c n op ipos)))) 
 
(defn check-options 
  "If none options left, then calls 'jumps' with c = -1. Recursivly it checks 
  all the options to see if one of them returns the board from 'jumps'." 
  [board c n op ipos] 
  (if (empty? op) 
    (jumps board [] -1 n ipos) 
    (let [jps (jumps (assoc-in board (first op) c) (first op) (inc c) n ipos)] 
      (if-not (empty? jps) 
          jps 
          (check-options board c n (rest op) ipos))))) 
 
(defn start 
  "Takes a number and return an error if it's an odd one. And if 
  is not, returns the board with the solved Closed knight's tour 
  in a board of size n." 
  [n] 
  (if (odd? n) 
    (println "Only even numbers for de size of the board") 
    (let [pos [(/ n 2) (/ n 2)]] 
      (jumps (assoc-in (board-f n) pos 1) pos 2 n pos)))) 
 
 
;; --- Printing The Board --- ;; 
(defn digits 
  "Returns the digists of a number. Ex: (n = 666) => (6 6 6)." 
  [n] 
  (->> n str (map (comp read-string str)))) 
 
(defn cute-board 
  "Prints a board of a visual and conforable way." 
  [n] 
  (let [b (start n) 
        l (inc (count (digits (* n n))))] 
    (println "\n") 
    (map #(println %) 
      (for [x b] 
        (apply str (map #(str (apply str 
                                     (take (- l (count (digits %))) 
                                           (repeat " "))) (str %)) x)))))) 
 
;; (cute-board 6) 
;; => 
;; 25  6 27 10 23  8 
;; 28 17 24  7 30 11 
;;  5 26 29 32  9 22 
;; 16 33 18  1 12 31 
;; 19  4 35 14 21  2 
;; 34 15 20  3 36 13 
 
;; (cute-board 14) 
;; => 
;; 37  44   5  32  35  70  75  30  73  90  77  28  81  84 
;; 6  33  36  69   4  31  72  91  76  29  86  83  78  27 
;; 43  38  45  34  71  92 123  74 105 112  89  80  85  82 
;; 46   7  68  93 122   3 104 113 124  87 106 111  26  79 
;; 39  42  47  96 103 136 121 126 129 114 119  88 107 110 
;;  8  67  40 137  94 127   2 135 120 125 130 109 116  25 
;; 41  48  95 102  97 138 141 128 167 134 115 118 131 108 
;; 66   9  98  61 140 157 168   1 142 165 170 133  24 117 
;; 49  62  65 156 101 160 139 166 169 196 143 176 171 132 
;; 10  99  60 151  64 155 158 181 164 175 190 187 144  23 
;; 59  50  63 100 159 150 161 174 195 182 177 172 189 186 
;; 14  11 152  57 154  55 180 163 178 173 188 191  22 145 
;; 51  58  13  16  53 162 149  18 183 194 147  20 185 192 
;; 12  15  52 153  56  17  54 179 148  19 184 193 146  21 
 
;; (cute-board 18) 
;; => 
;;  47  42  55   6  49  40  57  36  89  38 109  34  91 104 101  32  93  96 
;;  54   7  48  41  56   5  50  39 110  35  90 103 154  33  92  95 100  31 
;;  43  46  53  64  51  58  77  88  37 108 153 158 105 102 155 166  97  94 
;;   8  63  44  59  76  87   4 111 152 159 106 179 156 165 176  99  30 167 
;;  45  60  67  52  65  78 151 160 107 180 157 164 217 178 211 168 175  98 
;;  68   9  62  75  86 161 112   3 184 163 218 181 226 213 216 177 210  29 
;;  61  72  81  66  79 150 185 162 219 182 227 224 215 234 231 212 169 174 
;;  10  69  74  85 186 113 220 183   2 223 252 237 232 225 214 235  28 209 
;;  73  82  71  80 149 190 187 222 251 238 277 228 253 236 233 230 173 170 
;;  70  11  84 189 114 221 250 239 276   1 254 263 280 229 256 171 208  27 
;;  83 130 115 148 191 188 247 266 249 278 285 324 255 262 281 206 257 172 
;;  12 133 192 131 242 147 240 275 286 305 264 279 290 311 258 261  26 207 
;; 129 116 145 136 193 246 267 248 265 284 289 306 323 282 291 300 205 260 
;; 134  13 132 243 146 241 194 287 274 307 304 283 310 315 312 259 292  25 
;; 117 128 135 144 137 268 245 272 195 288 309 316 303 322 301 314 299 204 
;;  14 123 120 127 244 143 140 269 308 273 198 321 318 313 298 295  24 293 
;; 121 118 125  16 141 138 271  18 199 196 317  20 201 302 319  22 203 296 
;; 124  15 122 119 126  17 142 139 270  19 200 197 320  21 202 297 294  23 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.