Page List

Friday, August 17, 2012

Tkinter Knight's Tour Demo

This code is based on the Tcl knightstour.tcl demo written by Pat Thoyts. The demo uses a Canvas widget (to display a chessboard), a Text widget, a Button, CheckboxButton, and Scale (to control the tour).

Initially, a chessboard is displayed with a single chess piece, a black knight, who may be dragged to another square. Below the board are three controls: a Start button, a Repeat checkbox and a Speed scale. Pressing Start begins the tour which is calculated using an enhanced Warnsdorff's rule (see the original tcl file for more info). As the knight begins to move around the board, the position changes are recorded in the text widget to the right of the board. Drag the scale to change the speed with which the knight is moved. Click the Repeat checkbox to run random tours continuously.

Note that the knight will disappear if dragged off the board; hit Start to have him repositioned.




# File: knightstour.py
#    http://infohost.nmt.edu/tcc/help/pubs/tkinter//canvas.html
#    http://www.fileformat.info/info/unicode/char/265e/index.htm
#    http://opensource.apple.com/source/tcl/tcl-87/tk/tk/library/demos/knightstour.tcl

import random

from tkinter import *
from tkinter import ttk
from tkinter.font import Font

from demopanels import MsgPanel, SeeDismissPanel

class KnightsTourDemo(ttk.Frame):
    
    def __init__(self, isapp=True, name='knightstourdemo'):
        ttk.Frame.__init__(self, name=name)
        self.pack(expand=Y, fill=BOTH)
        self.master.title('Knights Tour Canvas Demo')
        self.isapp = isapp
        self._create_widgets()
        
    def _create_widgets(self):
        if self.isapp:
            # message panel not required          
            SeeDismissPanel(self)
        
        self._create_demo_panel()
        
    def _create_demo_panel(self):
        demoPanel = Frame(self, name='demo')
        demoPanel.pack(side=TOP, fill=BOTH, expand=Y)
        
        board = self._create_tour(demoPanel)
        self._add_bindings(board)
        
    def _create_tour(self, parent):
        c = Canvas(parent, width=240, height=240, name='board')
        self._draw_board(c)
        
        txt = Text(parent, width=10, height=1, name='dlg',
                   background='white', font=('Arial', 8))
        vscroll = ttk.Scrollbar(parent, orient=VERTICAL,
                                command=txt.yview)
        txt['yscrollcommand'] = vscroll.set
        controls = self._create_controls(parent, c)

        # position and configure resize behaviour
        c.grid(row=0, column=0, sticky='news')
        txt.grid(row=0, column=1, sticky='news')
        vscroll.grid(row=0, column=2, sticky='news')
        controls.grid(row=1, column=0, columnspan=3,
                      sticky=N+E)
        
        parent.rowconfigure(0, weight=1)
        parent.columnconfigure(1, weight=1)
        
        return c                

    def _draw_board(self, canvas):   
        # draw checkerboard
        for r in range(7, -1, -1):
            for c in range(8):
                if c&1 ^ r&1:
                    fill = 'tan3'
                    dfill = 'tan4'
                else:
                    fill = 'bisque'
                    dfill= 'bisque3'
                coords = (c*30+4, r*30+4, c*30+30, r*30+30)
                canvas.create_rectangle(coords,
                                        fill=fill,
                                        disabledfill=dfill,
                                        width=2,
                                        state='disabled')
                
        # create knight
        canvas.create_text(0, 0, font=('Courier 20'), text='\u265e',
                           anchor='nw', tags='knight',
                           fill='black', activefill='#600000')
        
        # randomly place him on the board
        self._put_random_knight(canvas)
                
    def _create_controls(self, parent, canvas):
        # board controls
        delay = IntVar()
        continuous = BooleanVar()
        
        frame = ttk.Frame(parent, name='controls')
        ttk.Label(frame, text='Speed').pack(side=RIGHT, padx=(4,24), pady=12)
        ttk.Scale(frame, from_=8, to=2000,
                  variable=delay).pack(side=RIGHT, padx=4, pady=12)
        ttk.Checkbutton(frame, text='Repeat',
                        variable=continuous).pack(side=RIGHT, padx=4, pady=12)
        btn = ttk.Button(frame, text='Start', name='start')
        btn['command'] = self._start_tour
        btn.pack(side=RIGHT, padx=(16,4), pady=12)        

        # set variable values and safe a reference to them        
        delay.set(600)
        continuous.set(False)
        canvas.__delay = delay
        canvas.__continuous = continuous
        
        return frame
                                
    # ========================================================================
    # Bindings
    # ========================================================================
    def _add_bindings(self, board):
        board.tag_bind('knight', '<1>', 
                       lambda e, b=board: self._start_drag(e, b))
        board.tag_bind('knight', '<B1-Motion>', 
                       lambda e, b=board: self._drag(e,b))
        board.tag_bind('knight', '<ButtonRelease-1>', 
                       lambda e, b=board: self._end_drag(e,b))    
                
    # ========================================================================
    # Bound methods
    # ========================================================================
                                
    def _start_drag(self, evt, board):
        # save drag start coords
        board.__lastX = board.canvasx(evt.x)
        board.__lastY = board.canvasy(evt.y)
    
    def _drag(self, evt, board):
        # move the knight with the mouse
        x = board.canvasx(evt.x)
        y = board.canvasy(evt.y)
        board.move(CURRENT, x-board.__lastX, y-board.__lastY)
        board.__lastX = x
        board.__lastY = y
        
    def _end_drag(self, evt, board):
        # place the knight in the square closest to
        # the mouse position
        square = board.find_closest(evt.x, evt.y, 0, 65)
        coords = board.coords(square)        
        board.coords(CURRENT, (coords[0], coords[1]))

    # ========================================================================
    # Commands
    # ========================================================================

    def _start_tour(self, square=None):        
        # start a new Knight's Tour
        self._toggle_start_btn('disabled')    
    
        b = self.nametowidget('demo.board')     # board
        t = self.nametowidget('demo.dlg')       # text 
        
        t.delete(1.0, END)    # clear text
        visited = []          # squares visited in this tour
        
        for n in range(64):
            b.itemconfigure(n, {'state': 'disabled',
                                'outline': 'black'})
        
        if not square:
            # get start position from current placement of knight
            coords = b.coords('knight')
            square = b.find_closest(coords[0], coords[1], 0, 65)

        if square[0] > 64:
            # knight is off the board
            self._put_random_knight(b)
            coords = b.coords('knight')
            square = b.find_closest(coords[0], coords[1], 0, 65)
                
        square = (square[0]-1, )
        b.__initial = square    # save starting square
        
        self._move_piece(b, t, square, square, visited)


    # ========================================================================
    # Chessboard methods
    # ========================================================================
    def _toggle_start_btn(self, newState):
        sbtn = self.nametowidget('demo.controls.start')
        sbtn.configure(state=newState)
        
    def _put_random_knight(self, board):
        # randomly choose a board square and position
        # the knight
        sqr = int( 1 + random.random() * 64)
        coords = board.coords((sqr, ))
        board.coords('knight', (coords[0], coords[1]))
        
    def _move_piece(self, b, txt, last, square, visited):
        # b - chess board (canvas)
        # txt - text console 
        # last - last square visited
        # square - current square    
        
        # display the square moves using standard
        # chess nomenclature
        chessSqr = '{}. {} .. {}\n'.format(len(visited),
                                    self._chess_sqr(last),
                                    self._chess_sqr(square) )
        txt.insert(END, chessSqr )
        txt.see(END)
        
        # configure squares, move the knight and update visited squares
        b.itemconfigure(1+last[0], state='normal', outline='black')
        b.itemconfigure(1+square[0], state='normal', outline='red')
        coords = b.coords(1+square[0])
        b.coords('knight', (coords[0], coords[1]))
        visited.append(square[0])
        
        # get the next move
        next = self._next_square(square[0], visited)
        if next != -1:
            # new legal move, pause and then move the knight
            self.after(b.__delay.get(), self._move_piece, b, txt, square, (next,), visited)           
        else:
            # no legal moves left
            if len(visited) == 64:
                if b.__initial == square:
                    txt.insert(END, 'Closed tour!\n')
                    self._toggle_start_btn('normal')
                else:
                    txt.insert(END, 'Success\n')
                    self._toggle_start_btn('normal')
                    if b.__continuous.get():
                        self.after(b.__delay.get() * 2,
                                   self._start_tour,
                                   self._put_random_knight(b))
            else:
                txt.insert(END, 'Failed!\n')
                self._toggle_start_btn('normal')
                
        return    
                
    def _chess_sqr(self, square):
        # Display a square number as a standard chess square notation.
        return '{}{}'.format(chr(97 + square[0]%8), square[0]//8 + 1)
                
    def _valid_moves(self, square):
        # Return a list of squares accessible from the given square
        moves = []
        pairs = [(-1,-2), (-2,-1), (-2,1), (-1,2), (1,2), (2,1), (2,-1), (1,-2)]
        for p in pairs :
            col = (square % 8) + p[0]
            row = (square // 8) + p[1]
            if (-1 < row < 8) and (-1 < col < 8):
                moves.append(row * 8 + col)
         
        return moves        
    
    def _check_squares(self, square, visited):
        # Return the number of available moves for this square
        moves = 0
        for test in self._valid_moves(square):
            if test not in visited:
                moves += 1
                
        return moves        

    def _next_square(self, square, visited):
        # Select the next square to move to. 
        # Returns -1 if no valid moves left
        minimum = 9
        nextSqr = -1
        for t in self._valid_moves(square):
            if t not in visited:
                count = self._check_squares(t, visited)
                if count < minimum:
                    minimum = count
                    nextSqr = t
                elif count == minimum:
                    nextSqr = self._edgemost(nextSqr, t)
                    
        return nextSqr

    def _edgemost(self, a, b):
        # Select the square nearest the edge of the board        
        colA = 3 - int(abs(3.5 - (a % 8)))
        colB = 3 - int(abs(3.5 - (b % 8)))
        rowA = 3 - int(abs(3.5 - (a // 8)))
        rowB = 3 - int(abs(3.5 - (b // 8)))
        
        if (colA * rowA) < (colB * rowB):
            return a
        else:
            return b
    
if __name__ == '__main__':
    KnightsTourDemo().mainloop()