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