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