Added a Knights tour canvas demo.

3 files changed, 254 insertions, 1 deletions

diff --git a/ChangeLog b/ChangeLog
index ec64826..9570b5a 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+2008-02-29  Pat Thoyts  <patthoyts@users.sourceforge.net>
+
+	* library/demos/widget:  Added a Knight's tour canvas demo.
+	* library/demos/knightstour.tcl:
+
 2008-02-27  Daniel Steffen  <das@users.sourceforge.net>
 
 	* macosx/tkMacOSXDraw.c: workaround leak in Carbon SetPortPenPixPat()
diff --git a/library/demos/knightstour.tcl b/library/demos/knightstour.tcl
new file mode 100644
index 0000000..93f8b47
--- /dev/null
+++ b/library/demos/knightstour.tcl
@@ -0,0 +1,247 @@
+# 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.
+
+package require Tk 8.5
+
+# Return a list of accessible squares from a given square
+proc ValidMoves {square} {
+    set moves {}
+    foreach pair {{-1 -2} {-2 -1} {-2 1} {-1 2} {1 2} {2 1} {2 -1} {1 -2}} {
+        set col [expr {($square % 8) + [lindex $pair 0]}]
+        set row [expr {($square / 8) + [lindex $pair 1]}]
+        if {$row > -1 && $row < 8 && $col > -1 && $col < 8} {
+            lappend moves [expr {$row * 8 + $col}]
+        }
+    }
+    return $moves
+}
+
+# Return the number of available moves for this square
+proc CheckSquare {square} {
+    variable visited
+    set moves 0
+    foreach test [ValidMoves $square] {
+        if {[lsearch -exact -integer $visited $test] == -1} {
+            incr moves
+        }
+    }
+    return $moves
+}
+
+# Select the next square to move to. Returns -1 if there are no available
+# squares remaining that we can move to.
+proc Next {square} {
+    variable visited
+    set minimum 9
+    set nextSquare -1
+    foreach testSquare [ValidMoves $square] {
+        if {[lsearch -exact -integer $visited $testSquare] == -1} {
+            set count [CheckSquare $testSquare]
+            if {$count < $minimum} {
+                set minimum $count
+                set nextSquare $testSquare
+            } elseif {$count == $minimum} {
+                set nextSquare [Edgemost $nextSquare $testSquare]
+            }
+        }
+    }
+    return $nextSquare
+}
+
+# Select the square nearest the edge of the board
+proc Edgemost {a b} {
+    set colA [expr {3-int(abs(3.5-($a%8)))}]
+    set colB [expr {3-int(abs(3.5-($b%8)))}]
+    set rowA [expr {3-int(abs(3.5-($a/8)))}]
+    set rowB [expr {3-int(abs(3.5-($b/8)))}]
+    return [expr {($colA * $rowA) < ($colB * $rowB) ? $a : $b}]
+}
+
+# Display a square number as a standard chess square notation.
+proc N {square} {
+    return [format %c%d [expr {97 + $square % 8}] \
+                [expr {$square / 8 + 1}]]
+}
+
+# Perform a Knight's move and schedule the next move.
+proc MovePiece {dlg last square} {
+    variable visited
+    variable delay
+    variable continuous
+    $dlg.f.txt insert end "[llength $visited]. [N $last] .. [N $square]\n" {}
+    $dlg.f.txt see end
+    $dlg.f.c itemconfigure [expr {1+$last}] -state normal -outline black
+    $dlg.f.c itemconfigure [expr {1+$square}] -state normal -outline red
+    $dlg.f.c coords knight [lrange [$dlg.f.c coords [expr {1+$square}]] 0 1]
+    lappend visited $square
+    set next [Next $square]
+    if {$next ne -1} {
+        variable aid [after $delay [list MovePiece $dlg $square $next]]
+    } else {
+        $dlg.b1 configure -state normal
+        if {[llength $visited] == 64} {
+            variable initial
+            if {$initial == $square} {
+                $dlg.f.txt insert end "Closed tour!"
+            } else {
+                $dlg.f.txt insert end "Success\n" {}
+                if {$continuous} {
+                    after [expr {$delay * 2}] [namespace code \
+                        [list Tour $dlg [expr {int(rand() * 64)}]]]
+                }
+            }
+        } else {
+            $dlg.f.txt insert end "FAILED!\n" {}
+        }
+    }
+}
+
+# Begin a new tour of the board given a random start position
+proc Tour {dlg {square {}}} {
+    variable visited {}
+    $dlg.f.txt delete 1.0 end
+    $dlg.b1 configure -state disabled
+    for {set n 0} {$n < 64} {incr n} {
+        $dlg.f.c itemconfigure $n -state disabled -outline black
+    }
+    if {$square eq {}} {
+        set square [expr {[$dlg.f.c find closest \
+                               {*}[$dlg.f.c coords knight] 0 65]-1}]
+    }
+    variable initial $square
+    after idle [list MovePiece $dlg $initial $initial]
+}
+
+proc Stop {} {
+    variable aid
+    catch {after cancel $aid}
+}
+
+proc Exit {dlg} {
+    Stop
+    destroy $dlg
+}
+
+proc SetDelay {new} {
+    variable delay [expr {int($new)}]
+}
+
+proc DragStart {w x y} {
+    $w dtag selected
+    $w addtag selected withtag current
+    variable dragging [list $x $y]
+}
+proc DragMotion {w x y} {
+    variable dragging
+    if {[info exists dragging]} {
+        $w move selected [expr {$x - [lindex $dragging 0]}] \
+            [expr {$y - [lindex $dragging 1]}]
+        variable dragging [list $x $y]
+    }
+}
+proc DragEnd {w x y} {
+    set square [$w find closest $x $y 0 65]
+    $w coords selected [lrange [$w coords $square] 0 1]
+    $w dtag selected
+    variable dragging ; unset dragging
+}
+
+proc CreateGUI {} {
+    catch {destroy .knightstour}
+    set dlg [toplevel .knightstour]
+    wm title $dlg "Knights tour"
+    wm withdraw $dlg
+    set f [ttk::frame $dlg.f]
+    set c [canvas $f.c -width 240 -height 240]
+    text $f.txt -width 10 -height 1 -background white \
+        -yscrollcommand [list $f.vs set] -font {Arial 8}
+    ttk::scrollbar $f.vs -command [list $f.txt yview]
+
+    variable delay 600
+    variable continuous 0
+    ttk::label $dlg.ls -text Speed
+    ttk::scale $dlg.sc  -from 8 -to 2000 -command [list SetDelay] \
+        -variable [namespace which -variable delay]
+    ttk::checkbutton $dlg.cc -text Repeat \
+        -variable [namespace which -variable continuous]
+    ttk::button $dlg.b1 -text Start -command [list Tour $dlg]
+    ttk::button $dlg.b2 -text Exit -command [list Exit $dlg]
+    set square 0
+    for {set row 7} {$row != -1} {incr row -1} {
+        for {set col 0} {$col < 8} {incr col} {
+            if {(($col & 1) ^ ($row & 1))} {
+                set fill tan3 ; set dfill tan4
+            } else {
+                set fill bisque ; set dfill bisque3
+            }
+            set coords [list [expr {$col * 30 + 3}] [expr {$row * 30 + 3}] \
+                            [expr {$col * 30 + 29}] [expr {$row * 30 + 29}]]
+            $c create rectangle $coords -fill $fill -disabledfill $dfill \
+                -width 2 -state disabled
+        }
+    }
+    catch {eval font create KnightFont -size -24}
+    $c create text 0 0 -font KnightFont -text "\u265e" \
+        -anchor nw -tags knight -fill black -activefill "#600000"
+    $c coords knight [lrange [$c coords [expr {1 + int(rand() * 64)}]] 0 1]
+    $c bind knight <ButtonPress-1> [namespace code [list DragStart %W %x %y]]
+    $c bind knight <Motion> [namespace code [list DragMotion %W %x %y]]
+    $c bind knight <ButtonRelease-1> [namespace code [list DragEnd %W %x %y]]
+    
+    grid $c $f.txt $f.vs  -sticky news
+    grid rowconfigure    $f 0 -weight 1
+    grid columnconfigure $f 1 -weight 1
+
+    grid $f - - - - - -sticky news
+    set things [list $dlg.ls $dlg.sc $dlg.cc $dlg.b1]
+    if {![info exists ::widgetDemo]} {
+        lappend things $dlg.b2 [ttk::sizegrip $dlg.sg]
+    }
+    grid {*}$things -sticky e
+    if {[info exists ::widgetDemo]} {
+        grid [addSeeDismiss $dlg.buttons $dlg] - - - - - -sticky ew
+    }
+    
+    grid rowconfigure $dlg 0 -weight 1
+    grid columnconfigure $dlg 0 -weight 1
+
+    bind $dlg <Control-F2> {console show}
+    bind $dlg <Return> [list $dlg.b1 invoke]
+    bind $dlg <Escape> [list $dlg.b2 invoke]
+    bind $dlg <Destroy> [namespace code [list Stop]]
+    wm protocol $dlg WM_DELETE_WINDOW [namespace code [list Exit $dlg]]
+
+    wm deiconify $dlg
+    tkwait window $dlg
+}
+
+if {!$tcl_interactive} {
+    if {![winfo exists .knightstour]} {
+        if {![info exists widgetDemo]} { wm withdraw . }
+        set r [catch [linsert $argv 0 CreateGUI] err]
+        if {$r} {
+            tk_messageBox -icon error -title "Error" -message $err
+        }
+        if {![info exists widgetDemo]} { exit $r }
+    }
+}
diff --git a/library/demos/widget b/library/demos/widget
index 083e1d5..a8c2e84 100644
--- a/library/demos/widget
+++ b/library/demos/widget
@@ -10,7 +10,7 @@ exec wish "$0" "$@"
 # separate ".tcl" files is this directory, which are sourced by this script as
 # needed.
 #
-# RCS: @(#) $Id: widget,v 1.49 2007/12/13 15:27:07 dgp Exp $
+# RCS: @(#) $Id: widget,v 1.50 2008/02/29 22:48:07 patthoyts Exp $
 
 package require Tcl	8.5
 package require Tk	8.5
@@ -358,6 +358,7 @@ addFormattedText {
     @@demo ruler	A ruler with adjustable tab stops
     @@demo floor	A building floor plan
     @@demo cscroll	A simple scrollable canvas
+    @@demo knightstour  A Knight's tour of the chess board
 
     @@subtitle	Scales and Progress Bars
     @@demo hscale	Horizontal scale