summaryrefslogtreecommitdiff
path: root/jni/ruby/ext/tk/sample/demos-en/knightstour.rb
blob: 6f96a5be107f7d79261a40d54a6273a55e5051e0 (plain)
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
# Based on the widget demo of Tcl/Tk8.5.2
# The following is the original copyright text.
#----------------------------------------------------------------------------
# Copyright (C) 2008 Pat Thoyts <patthoyts@users.sourceforge.net>
#
#       Calculate a Knight's tour of a chessboard.
#
#       This uses Warnsdorff's rule to calculate the next square each
#       time. This specifies that the next square should be the one that
#       has the least number of available moves.
#
#       Using this rule it is possible to get to a position where
#       there are no squares available to move into. In this implementation
#       this occurs when the starting square is d6.
#
#       To solve this fault an enhancement to the rule is that if we
#       have a choice of squares with an equal score, we should choose
#       the one nearest the edge of the board.
#
#       If the call to the Edgemost function is commented out you can see
#       this occur.
#
#       You can drag the knight to a specific square to start if you wish.
#       If you let it repeat then it will choose random start positions
#       for each new tour.
#----------------------------------------------------------------------------
require 'tk'

class Knights_Tour
  # Return a list of accessible squares from a given square
  def valid_moves(square)
    moves = []
    [
      [-1,-2], [-2,-1], [-2,1], [-1,2], [1,2], [2,1], [2,-1], [1,-2]
    ].each{|col_delta, row_delta|
      col = (square % 8) + col_delta
      row = (square.div(8)) + row_delta
      moves << (row * 8 + col) if row > -1 && row < 8 && col > -1 && col < 8
    }
    moves
  end

  # Return the number of available moves for this square
  def check_square(square)
    valid_moves(square).find_all{|pos| ! @visited.include?(pos)}.length
  end

  # Select the next square to move to. Returns -1 if there are no available
  # squares remaining that we can move to.
  def next_square(square)
    minimum = 9
    nxt = -1
    valid_moves(square).each{|pos|
      unless @visited.include?(pos)
        cnt = check_square(pos)
        if cnt < minimum
          minimum = cnt
          nxt = pos
        elsif cnt == minimum
          nxt = edgemost(nxt, pos)
        end
      end
    }
    nxt
  end

  # Select the square nearest the edge of the board
  def edgemost(nxt, pos)
    col_A = 3 - ((3.5 - nxt % 8).abs.to_i)
    col_B = 3 - ((3.5 - pos % 8).abs.to_i)
    row_A = 3 - ((3.5 - nxt.div(8)).abs.to_i)
    row_B = 3 - ((3.5 - pos.div(8)).abs.to_i)
    (col_A * row_A < col_B * row_B)? nxt : pos
  end

  # Display a square number as a standard chess square notation.
  def _N(square)
    '%c%d' % [(97 + square % 8), (square.div(8) + 1)]
  end

  # Perform a Knight's move and schedule the next move.
  def move_piece(last, square)
    @log.insert(:end, "#{@visited.length}. #{_N last} -> #{_N square}\n", '')
    @log.see(:end)
    @board.itemconfigure(1+last, :state=>:normal, :outline=>'black')
    @board.itemconfigure(1+square, :state=>:normal, :outline=>'red')
    @knight.coords(@board.coords(1+square)[0..1])
    @visited << square
    if (nxt = next_square(square)) != -1
      @after_id = Tk.after(@delay.numeric){move_piece(square, nxt) rescue nil}
    else
      @start_btn.state :normal
      if @visited.length == 64
        if @initial == square
          @log.insert :end, 'Closed tour!'
        else
          @log.insert :end, "Success\n", {}
          Tk.after(@delay.numeric * 2){tour(rand(64))} if @continuous.bool
        end
      else
        @log.insert :end, "FAILED!\n", {}
      end
    end
  end

  # Begin a new tour of the board given a random start position
  def tour(square = nil)
    @visited.clear
    @log.clear
    @start_btn.state :disabled
    1.upto(64){|n|
      @board.itemconfigure(n, :state=>:disabled, :outline=>'black')
    }
    unless square
      square = @board.find_closest(*(@knight.coords << 0 << 65))[0].to_i - 1
    end
    @initial = square
    Tk.after_idle{ move_piece(@initial, @initial) rescue nil }
  end

  def _stop
    Tk.after_cancel(@after_id) rescue nil
  end

  def _exit
    _stop
    $knightstour.destroy
  end

  def set_delay(new)
    @delay.numeric = new.to_i
  end

  def drag_start(w, x, y)
    w.dtag('selected')
    w.addtag('selected', :withtag, 'current')
    @dragging = [x, y]
  end

  def drag_motion(w, x, y)
    return unless @dragging
    w.move('selected', x - @dragging[0], y - @dragging[1])
    @dragging = [x, y]
  end

  def drag_end(w, x, y)
    square = w.find_closest(x, y, 0, 65)
    w.coords('selected', w.coords(square)[0..1])
    w.dtag('selected')
    @dragging = nil
  end

  def make_SeeDismiss
    ## See Code / Dismiss
    frame = Ttk::Frame.new($knightstour)
    sep = Ttk::Separator.new(frame)
    Tk.grid(sep, :columnspan=>4, :row=>0, :sticky=>'ew', :pady=>2)
    TkGrid('x',
           Ttk::Button.new(frame, :text=>'See Code',
                           :image=>$image['view'], :compound=>:left,
                           :command=>proc{showCode 'knightstour'}),
           Ttk::Button.new(frame, :text=>'Dismiss',
                           :image=>$image['delete'], :compound=>:left,
                           :command=>proc{
                             $knightstour.destroy
                             $knightstour = nil
                           }),
           :padx=>4, :pady=>4)
    frame.grid_columnconfigure(0, :weight=>1)
    frame
  end

  def create_gui(parent = nil)
    $knightstour.destroy rescue nil
    $knightstour = Tk::Toplevel.new(parent, :title=>"Knight's tour")
    $knightstour.withdraw
    base_f = Ttk::Frame.new($knightstour)
    @board = Tk::Canvas.new(base_f, :width=>240, :height=>240)
    @log = Tk::Text.new(base_f, :width=>12, :height=>1,
                        :font=>'Arial 8', :background=>'white')
    scr = @log.yscrollbar(Ttk::Scrollbar.new(base_f))

    @visited = []
    @delay = TkVariable.new(600)
    @continuous = TkVariable.new(false)

    tool_f = Ttk::Frame.new($knightstour)
    label = Ttk::Label.new(tool_f, :text=>'Speed')
    scale = Ttk::Scale.new(tool_f, :from=>8, :to=>2000, :variable=>@delay,
                           :command=>proc{|n| set_delay(n)})
    check = Ttk::Checkbutton.new(tool_f, :text=>'Repeat',
                                 :variable=>@continuous)
    @start_btn = Ttk::Button.new(tool_f, :text=>'Start',
                                 :command=>proc{tour()})
    @exit_btn = Ttk::Button.new(tool_f, :text=>'Exit',
                                :command=>proc{_exit()})

    7.downto(0){|row|
      0.upto(7){|col|
        if ((col & 1) ^ (row & 1)).zero?
          fill  = 'bisque'
          dfill = 'bisque3'
        else
          fill  = 'tan3'
          dfill = 'tan4'
        end
        coords = [col * 30 + 4, row * 30 + 4, col * 30 + 30, row * 30 + 30]
        @board.create(TkcRectangle, coords,
                      :fill=>fill, :disabledfill=>dfill,
                      :width=>2, :state=>:disabled)
      }
    }

    @knight_font = TkFont.new(:size=>-24)
    @knight = TkcText.new(@board, 0, 0, :font=>@knight_font,
                          :text=>Tk::UTF8_String.new('\u265e'),
                          :anchor=>'nw', # :tags=>'knight',
                          :fill=>'black', :activefill=>'#600000')
    @knight.coords(@board.coords(rand(64)+1)[0..1])
    @knight.bind('ButtonPress-1', '%W %x %y'){|w,x,y| drag_start(w,x,y)}
    @knight.bind('Motion', '%W %x %y'){|w,x,y| drag_motion(w,x,y)}
    @knight.bind('ButtonRelease-1', '%W %x %y'){|w,x,y| drag_end(w,x,y)}

    Tk.grid(@board, @log, scr, :sticky=>'news')
    base_f.grid_rowconfigure(0, :weight=>1)
    base_f.grid_columnconfigure(0, :weight=>1)

    Tk.grid(base_f, '-', '-', '-', '-', '-', :sticky=>'news')
    widgets = [label, scale, check, @start_btn]
    sg = nil
    unless $RubyTk_WidgetDemo
      widgets << @exit_btn
      if Tk.windowingsystem != 'aqua'
        #widgets.unshift(Ttk::SizeGrip.new(tool_f))
        Ttk::SizeGrip.new(tool_f).pack(:side=>:right, :anchor=>'se')
      end
    end
    Tk.pack(widgets, :side=>:right)
    if Tk.windowingsystem == 'aqua'
      TkPack.configure(widgets, :padx=>[4, 4], :pady=>[12, 12])
      TkPack.configure(widgets[0], :padx=>[4, 24])
      TkPack.configure(widgets[-1], :padx=>[16, 4])
    end

    Tk.grid(tool_f, '-', '-', '-', '-', '-', :sticky=>'ew')

    if $RubyTk_WidgetDemo
      Tk.grid(make_SeeDismiss(), '-', '-', '-', '-', '-', :sticky=>'ew')
    end

    $knightstour.grid_rowconfigure(0, :weight=>1)
    $knightstour.grid_columnconfigure(0, :weight=>1)

    $knightstour.bind('Control-F2'){TkConsole.show}
    $knightstour.bind('Return'){@start_btn.invoke}
    $knightstour.bind('Escape'){@exit_btn.invoke}
    $knightstour.bind('Destroy'){ _stop }
    $knightstour.protocol('WM_DELETE_WINDOW'){ _exit }

    $knightstour.deiconify
    $knightstour.tkwait_destroy
  end

  def initialize(parent = nil)
    create_gui(parent)
  end
end

Tk.root.withdraw unless $RubyTk_WidgetDemo
Thread.new{Tk.mainloop} if __FILE__ == $0
Knights_Tour.new