1# Based on the widget demo of Tcl/Tk8.5.2 2# The following is the original copyright text. 3#---------------------------------------------------------------------------- 4# Copyright (C) 2008 Pat Thoyts <patthoyts@users.sourceforge.net> 5# 6# Calculate a Knight's tour of a chessboard. 7# 8# This uses Warnsdorff's rule to calculate the next square each 9# time. This specifies that the next square should be the one that 10# has the least number of available moves. 11# 12# Using this rule it is possible to get to a position where 13# there are no squares available to move into. In this implementation 14# this occurs when the starting square is d6. 15# 16# To solve this fault an enhancement to the rule is that if we 17# have a choice of squares with an equal score, we should choose 18# the one nearest the edge of the board. 19# 20# If the call to the Edgemost function is commented out you can see 21# this occur. 22# 23# You can drag the knight to a specific square to start if you wish. 24# If you let it repeat then it will choose random start positions 25# for each new tour. 26#---------------------------------------------------------------------------- 27require 'tk' 28 29class Knights_Tour 30 # Return a list of accessible squares from a given square 31 def valid_moves(square) 32 moves = [] 33 [ 34 [-1,-2], [-2,-1], [-2,1], [-1,2], [1,2], [2,1], [2,-1], [1,-2] 35 ].each{|col_delta, row_delta| 36 col = (square % 8) + col_delta 37 row = (square.div(8)) + row_delta 38 moves << (row * 8 + col) if row > -1 && row < 8 && col > -1 && col < 8 39 } 40 moves 41 end 42 43 # Return the number of available moves for this square 44 def check_square(square) 45 valid_moves(square).find_all{|pos| ! @visited.include?(pos)}.length 46 end 47 48 # Select the next square to move to. Returns -1 if there are no available 49 # squares remaining that we can move to. 50 def next_square(square) 51 minimum = 9 52 nxt = -1 53 valid_moves(square).each{|pos| 54 unless @visited.include?(pos) 55 cnt = check_square(pos) 56 if cnt < minimum 57 minimum = cnt 58 nxt = pos 59 elsif cnt == minimum 60 nxt = edgemost(nxt, pos) 61 end 62 end 63 } 64 nxt 65 end 66 67 # Select the square nearest the edge of the board 68 def edgemost(nxt, pos) 69 col_A = 3 - ((3.5 - nxt % 8).abs.to_i) 70 col_B = 3 - ((3.5 - pos % 8).abs.to_i) 71 row_A = 3 - ((3.5 - nxt.div(8)).abs.to_i) 72 row_B = 3 - ((3.5 - pos.div(8)).abs.to_i) 73 (col_A * row_A < col_B * row_B)? nxt : pos 74 end 75 76 # Display a square number as a standard chess square notation. 77 def _N(square) 78 '%c%d' % [(97 + square % 8), (square.div(8) + 1)] 79 end 80 81 # Perform a Knight's move and schedule the next move. 82 def move_piece(last, square) 83 @log.insert(:end, "#{@visited.length}. #{_N last} -> #{_N square}\n", '') 84 @log.see(:end) 85 @board.itemconfigure(1+last, :state=>:normal, :outline=>'black') 86 @board.itemconfigure(1+square, :state=>:normal, :outline=>'red') 87 @knight.coords(@board.coords(1+square)[0..1]) 88 @visited << square 89 if (nxt = next_square(square)) != -1 90 @after_id = Tk.after(@delay.numeric){move_piece(square, nxt) rescue nil} 91 else 92 @start_btn.state :normal 93 if @visited.length == 64 94 if @initial == square 95 @log.insert :end, 'Closed tour!' 96 else 97 @log.insert :end, "Success\n", {} 98 Tk.after(@delay.numeric * 2){tour(rand(64))} if @continuous.bool 99 end 100 else 101 @log.insert :end, "FAILED!\n", {} 102 end 103 end 104 end 105 106 # Begin a new tour of the board given a random start position 107 def tour(square = nil) 108 @visited.clear 109 @log.clear 110 @start_btn.state :disabled 111 1.upto(64){|n| 112 @board.itemconfigure(n, :state=>:disabled, :outline=>'black') 113 } 114 unless square 115 square = @board.find_closest(*(@knight.coords << 0 << 65))[0].to_i - 1 116 end 117 @initial = square 118 Tk.after_idle{ move_piece(@initial, @initial) rescue nil } 119 end 120 121 def _stop 122 Tk.after_cancel(@after_id) rescue nil 123 end 124 125 def _exit 126 _stop 127 $knightstour.destroy 128 end 129 130 def set_delay(new) 131 @delay.numeric = new.to_i 132 end 133 134 def drag_start(w, x, y) 135 w.dtag('selected') 136 w.addtag('selected', :withtag, 'current') 137 @dragging = [x, y] 138 end 139 140 def drag_motion(w, x, y) 141 return unless @dragging 142 w.move('selected', x - @dragging[0], y - @dragging[1]) 143 @dragging = [x, y] 144 end 145 146 def drag_end(w, x, y) 147 square = w.find_closest(x, y, 0, 65) 148 w.coords('selected', w.coords(square)[0..1]) 149 w.dtag('selected') 150 @dragging = nil 151 end 152 153 def make_SeeDismiss 154 ## See Code / Dismiss 155 frame = Ttk::Frame.new($knightstour) 156 sep = Ttk::Separator.new(frame) 157 Tk.grid(sep, :columnspan=>4, :row=>0, :sticky=>'ew', :pady=>2) 158 TkGrid('x', 159 Ttk::Button.new(frame, :text=>'See Code', 160 :image=>$image['view'], :compound=>:left, 161 :command=>proc{showCode 'knightstour'}), 162 Ttk::Button.new(frame, :text=>'Dismiss', 163 :image=>$image['delete'], :compound=>:left, 164 :command=>proc{ 165 $knightstour.destroy 166 $knightstour = nil 167 }), 168 :padx=>4, :pady=>4) 169 frame.grid_columnconfigure(0, :weight=>1) 170 frame 171 end 172 173 def create_gui(parent = nil) 174 $knightstour.destroy rescue nil 175 $knightstour = Tk::Toplevel.new(parent, :title=>"Knight's tour") 176 $knightstour.withdraw 177 base_f = Ttk::Frame.new($knightstour) 178 @board = Tk::Canvas.new(base_f, :width=>240, :height=>240) 179 @log = Tk::Text.new(base_f, :width=>12, :height=>1, 180 :font=>'Arial 8', :background=>'white') 181 scr = @log.yscrollbar(Ttk::Scrollbar.new(base_f)) 182 183 @visited = [] 184 @delay = TkVariable.new(600) 185 @continuous = TkVariable.new(false) 186 187 tool_f = Ttk::Frame.new($knightstour) 188 label = Ttk::Label.new(tool_f, :text=>'Speed') 189 scale = Ttk::Scale.new(tool_f, :from=>8, :to=>2000, :variable=>@delay, 190 :command=>proc{|n| set_delay(n)}) 191 check = Ttk::Checkbutton.new(tool_f, :text=>'Repeat', 192 :variable=>@continuous) 193 @start_btn = Ttk::Button.new(tool_f, :text=>'Start', 194 :command=>proc{tour()}) 195 @exit_btn = Ttk::Button.new(tool_f, :text=>'Exit', 196 :command=>proc{_exit()}) 197 198 7.downto(0){|row| 199 0.upto(7){|col| 200 if ((col & 1) ^ (row & 1)).zero? 201 fill = 'bisque' 202 dfill = 'bisque3' 203 else 204 fill = 'tan3' 205 dfill = 'tan4' 206 end 207 coords = [col * 30 + 4, row * 30 + 4, col * 30 + 30, row * 30 + 30] 208 @board.create(TkcRectangle, coords, 209 :fill=>fill, :disabledfill=>dfill, 210 :width=>2, :state=>:disabled) 211 } 212 } 213 214 @knight_font = TkFont.new(:size=>-24) 215 @knight = TkcText.new(@board, 0, 0, :font=>@knight_font, 216 :text=>Tk::UTF8_String.new('\u265e'), 217 :anchor=>'nw', # :tags=>'knight', 218 :fill=>'black', :activefill=>'#600000') 219 @knight.coords(@board.coords(rand(64)+1)[0..1]) 220 @knight.bind('ButtonPress-1', '%W %x %y'){|w,x,y| drag_start(w,x,y)} 221 @knight.bind('Motion', '%W %x %y'){|w,x,y| drag_motion(w,x,y)} 222 @knight.bind('ButtonRelease-1', '%W %x %y'){|w,x,y| drag_end(w,x,y)} 223 224 Tk.grid(@board, @log, scr, :sticky=>'news') 225 base_f.grid_rowconfigure(0, :weight=>1) 226 base_f.grid_columnconfigure(0, :weight=>1) 227 228 Tk.grid(base_f, '-', '-', '-', '-', '-', :sticky=>'news') 229 widgets = [label, scale, check, @start_btn] 230 sg = nil 231 unless $RubyTk_WidgetDemo 232 widgets << @exit_btn 233 if Tk.windowingsystem != 'aqua' 234 #widgets.unshift(Ttk::SizeGrip.new(tool_f)) 235 Ttk::SizeGrip.new(tool_f).pack(:side=>:right, :anchor=>'se') 236 end 237 end 238 Tk.pack(widgets, :side=>:right) 239 if Tk.windowingsystem == 'aqua' 240 TkPack.configure(widgets, :padx=>[4, 4], :pady=>[12, 12]) 241 TkPack.configure(widgets[0], :padx=>[4, 24]) 242 TkPack.configure(widgets[-1], :padx=>[16, 4]) 243 end 244 245 Tk.grid(tool_f, '-', '-', '-', '-', '-', :sticky=>'ew') 246 247 if $RubyTk_WidgetDemo 248 Tk.grid(make_SeeDismiss(), '-', '-', '-', '-', '-', :sticky=>'ew') 249 end 250 251 $knightstour.grid_rowconfigure(0, :weight=>1) 252 $knightstour.grid_columnconfigure(0, :weight=>1) 253 254 $knightstour.bind('Control-F2'){TkConsole.show} 255 $knightstour.bind('Return'){@start_btn.invoke} 256 $knightstour.bind('Escape'){@exit_btn.invoke} 257 $knightstour.bind('Destroy'){ _stop } 258 $knightstour.protocol('WM_DELETE_WINDOW'){ _exit } 259 260 $knightstour.deiconify 261 $knightstour.tkwait_destroy 262 end 263 264 def initialize(parent = nil) 265 create_gui(parent) 266 end 267end 268 269Tk.root.withdraw unless $RubyTk_WidgetDemo 270Thread.new{Tk.mainloop} if __FILE__ == $0 271Knights_Tour.new 272