On Aug 12, 2006, at 5:15 PM, James Edward Gray II wrote: > In all fairness, I really would love to go back and add the solver, > but I am very, very busy this weekend. :( We will see if I can > steal the time. I found the time. Here are some fun timings with it: $ time ruby grid_fill.rb -s 19 ------------------------------------------------------------------------ ----- | 203 229 224 204 230 223 209 233 220 210 234 219 211 235 160 194 236 161 167 | | 268 174 201 34 173 200 35 172 199 352 171 198 312 170 197 163 169 196 164 | | 227 205 38 228 225 60 231 222 69 232 221 70 159 218 71 238 166 193 237 | | 202 33 269 207 36 55 208 353 54 213 311 351 212 310 313 195 309 162 168 | | 267 175 226 61 39 89 84 59 216 81 68 217 72 75 240 348 74 239 165 | | 270 206 37 56 97 65 53 98 66 354 99 79 158 350 78 307 314 192 308 | | 49 32 40 90 85 58 215 88 83 214 156 82 241 361 73 242 333 347 243 | | 266 176 110 62 52 111 128 64 116 80 67 355 100 76 319 349 77 306 315 | | 271 91 50 57 96 134 86 107 155 87 342 3 157 343 4 360 317 191 334 | | 48 31 41 112 129 63 115 130 127 17 119 104 320 1 103 303 332 346 244 | | 265 177 109 135 51 108 136 133 117 106 154 356 101 6 318 344 5 305 316 | | 272 92 45 28 95 143 126 18 148 131 341 2 120 302 331 359 283 190 335 | | 47 30 42 113 124 138 114 123 137 16 118 105 321 357 102 304 329 345 245 | | 264 178 26 144 44 27 149 132 340 11 153 293 338 7 284 301 336 250 282 | | 273 93 46 29 94 142 125 19 147 122 322 15 121 297 330 358 254 189 328 | | 182 24 43 290 25 139 291 12 150 292 339 10 285 294 337 251 281 300 246 | | 263 179 21 145 261 20 146 141 323 14 152 296 325 8 257 298 327 249 255 | | 274 289 183 275 288 184 276 287 185 277 286 186 278 252 187 279 253 188 280 | | 181 23 262 180 22 140 260 13 151 259 324 9 258 295 326 248 256 299 247 | ------------------------------------------------------------------------ ----- real 0m0.013s user 0m0.007s sys 0m0.005s $ time ruby grid_fill.rb -s 19 ------------------------------------------------------------------------ ----- | 282 308 303 283 309 302 288 312 299 289 313 298 290 314 239 273 315 240 246 | | 347 253 280 113 252 279 114 251 278 70 250 277 30 249 276 242 248 275 243 | | 306 284 117 307 304 139 310 301 148 311 300 149 238 297 150 317 245 272 316 | | 281 112 348 286 115 134 287 71 133 292 29 69 291 28 31 274 27 241 247 | | 346 254 305 140 118 168 163 138 295 160 147 296 151 154 319 66 153 318 244 | | 349 285 116 135 176 144 132 177 145 72 178 158 237 68 157 25 32 271 26 | | 128 111 119 169 164 137 294 167 162 293 235 161 320 79 152 321 51 65 322 | | 345 255 189 141 131 190 207 143 195 159 146 73 179 155 37 67 156 24 33 | | 350 170 129 136 175 213 165 186 234 166 60 82 236 61 83 78 35 270 52 | | 127 110 120 191 208 142 194 209 206 96 198 183 38 80 182 21 50 64 323 | | 344 256 188 214 130 187 215 212 196 185 233 74 180 85 36 62 84 23 34 | | 351 171 124 107 174 222 205 97 227 210 59 81 199 20 49 77 1 269 53 | | 126 109 121 192 203 217 193 202 216 95 197 184 39 75 181 22 47 63 324 | | 343 257 105 223 123 106 228 211 58 90 232 11 56 86 2 19 54 329 361 | | 352 172 125 108 173 221 204 98 226 201 40 94 200 15 48 76 333 268 46 | | 261 103 122 8 104 218 9 91 229 10 57 89 3 12 55 330 360 18 325 | | 342 258 100 224 340 99 225 220 41 93 231 14 43 87 336 16 45 328 334 | | 353 7 262 354 6 263 355 5 264 356 4 265 357 331 266 358 332 267 359 | | 260 102 341 259 101 219 339 92 230 338 42 88 337 13 44 327 335 17 326 | ------------------------------------------------------------------------ ----- real 0m0.012s user 0m0.007s sys 0m0.005s $ time ruby grid_fill.rb -s 19 ------------------------------------------------------------------------ ----- | 139 165 160 140 166 159 145 169 156 146 170 155 147 171 96 130 172 97 103 | | 204 110 137 331 109 136 332 108 135 288 107 134 248 106 133 99 105 132 100 | | 163 141 335 164 161 357 167 158 5 168 157 6 95 154 7 174 102 129 173 | | 138 330 205 143 333 352 144 289 351 149 247 287 148 246 249 131 245 98 104 | | 203 111 162 358 336 25 20 356 152 17 4 153 8 11 176 284 10 175 101 | | 206 142 334 353 33 1 350 34 2 290 35 15 94 286 14 243 250 128 244 | | 346 329 337 26 21 355 151 24 19 150 92 18 177 297 9 178 269 283 179 | | 202 112 46 359 349 47 64 361 52 16 3 291 36 12 255 285 13 242 251 | | 207 27 347 354 32 70 22 43 91 23 278 300 93 279 301 296 253 127 270 | | 345 328 338 48 65 360 51 66 63 314 55 40 256 298 39 239 268 282 180 | | 201 113 45 71 348 44 72 69 53 42 90 292 37 303 254 280 302 241 252 | | 208 28 342 325 31 79 62 315 84 67 277 299 56 238 267 295 219 126 271 | | 344 327 339 49 60 74 50 59 73 313 54 41 257 293 38 240 265 281 181 | | 200 114 323 80 341 324 85 68 276 308 89 229 274 304 220 237 272 186 218 | | 209 29 343 326 30 78 61 316 83 58 258 312 57 233 266 294 190 125 264 | | 118 321 340 226 322 75 227 309 86 228 275 307 221 230 273 187 217 236 182 | | 199 115 318 81 197 317 82 77 259 311 88 232 261 305 193 234 263 185 191 | | 210 225 119 211 224 120 212 223 121 213 222 122 214 188 123 215 189 124 216 | | 117 320 198 116 319 76 196 310 87 195 260 306 194 231 262 184 192 235 183 | ------------------------------------------------------------------------ ----- real 0m0.012s user 0m0.007s sys 0m0.005s It even always gets the bonus points for the circular solution. <laughs> OK, I admit finding circular solutions on the big boards sucks. ;) Here's the code: #!/usr/bin/env ruby -w require "enumerator" class PenAndPaperGame def self.circular_solutions @circular ||= if File.exist?("circular_solutions.dump") File.open("circular_solutions.dump") { |file| Marshal.load (file) } else Array.new end end def initialize(size) @size = size @largest = @size * @size @grid = Array.new(@largest) end def solve if self.class.circular_solutions[@size].nil? solve_manually else @grid = self.class.circular_solutions[@size] offset = @grid[rand(@grid.size)] @grid.map! { |n| (n + offset) % @largest + 1 } to_s end end def solve_manually x, y = rand(@size), rand(@size) count = mark(x, y) loop do to = jumps(x, y) return self.class.new(@size).solve_manually if to.empty? scores = rate_jumps(to) low = scores.min next_jump = to.enum_for(:each_with_index).select do |jump| scores[jump.last] == low end.sort_by { rand }.first.first count = mark(*(next_jump + [count])) x, y = next_jump if count > @largest if circular? self.class.circular_solutions[@size] = @grid File.open("circular_solutions.dump", "w") do |file| Marshal.dump(self.class.circular_solutions, file) end return to_s else puts "Found this solution:" puts to_s puts "Continuing search for a circular solution..." return self.class.new(@size).solve_manually end end end end def to_s width = @largest.to_s.size border = " -" + (["-" * width] * @size).join("-") + "- \n" border + @grid.enum_for(:each_slice, @size).inject(String.new) do |grid, row| grid + "| " + row.map { |n| n.to_s.center(width) }.join(" ") + " |\n" end + border end private def at(x, y) x + y * @size end def mark(current_x, current_y, mark = 1) @grid[at(current_x, current_y)] = mark mark + 1 end def jumps(from_x, from_y, grid = @grid) [ [-3, 0], [3, 0], [0, -3], [0, 3], [2, 2], [-2, 2], [2, -2], [-2, -2] ].map do |jump| [from_x + jump.first, from_y + jump.last] end.select do |jump| jump.all? { |to| (0...@size).include? to } and grid[at (*jump)].nil? end end def rate_jumps(choices) choices.map { |jump| jumps(*jump).size } end def circular? grid = @grid.dup grid[grid.index(@largest)] = nil x, y = grid.index(1).divmod(@size).reverse not jumps(x, y, grid).empty? end end if __FILE__ == $PROGRAM_NAME size = ARGV.first && ARGV.first =~ /\A-s(?:ize)?\Z/ ? ARGV.last.to_i : 5 puts PenAndPaperGame.new(size).solve end __END__ James Edward Gray II