Thread: The Knight's Tour.

Results 1 to 7 of 7
  1. #1 The Knight's Tour. 
    Extreme Donator


    Join Date
    Jul 2009
    Age
    27
    Posts
    4,351
    Thanks given
    826
    Thanks received
    1,239
    Rep Power
    1781

    Alright well since we don't get any challenges really around here, I would like to offer one just for the fun of the community.

    If any of you are familiar with the Knight's Tour, it's a problem in which you must move the Knight piece around the whole board and touch every square once.

    You can find more information on it here: Knight's tour - Wikipedia, the free encyclopedia

    What you need to do:
    • Create an application that will take the chess board and move the knight around the squares.
      • Language can be any possible, C#, Java, anything!
    • Note: Some kind of visual frame is not required but I think it would be cool.


    I don't mind if you make it print the current square in which the knight is travelling to, or if you make a 2d frame and make the piece move itself.

    I'm interested to see what people come up with, good luck! I will be submitting my code too after I start

    NOTE: You must label your tiles, here's the current labeling.


    You can find my GitHub here, for what I'm currently working on.
    Reply With Quote  
     

  2. Thankful users:


  3. #2  
    Banned

    Join Date
    Oct 2011
    Age
    27
    Posts
    2,566
    Thanks given
    1,027
    Thanks received
    1,168
    Rep Power
    0
    "A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once"


    ??
    Reply With Quote  
     

  4. #3  
    Extreme Donator


    Join Date
    Jul 2009
    Age
    27
    Posts
    4,351
    Thanks given
    826
    Thanks received
    1,239
    Rep Power
    1781
    Quote Originally Posted by Vip3r View Post
    "A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once"


    ??
    Not sure what you're asking, the point is to automatically make the application figure out the path. Not hard code it.

    You can find my GitHub here, for what I'm currently working on.
    Reply With Quote  
     

  5. #4  
    Banned

    Join Date
    Oct 2011
    Age
    27
    Posts
    2,566
    Thanks given
    1,027
    Thanks received
    1,168
    Rep Power
    0
    Quote Originally Posted by Sir Tom View Post
    Not sure what you're asking, the point is to automatically make the application figure out the path. Not hard code it.
    Oh I thought it was to make the game
    Reply With Quote  
     

  6. #5  
    ¯̿ ̿|̿ ̿ |̶ ̶ ̶ ̶| |̶͇̿ ̶͇̿ ͇̿ Haskelle

    Join Date
    Nov 2007
    Age
    29
    Posts
    1,227
    Thanks given
    329
    Thanks received
    517
    Rep Power
    1133
    Might try this one. Bruteforcing is not gonna work. that's for sure :/
    Monads are just Monoids in the category of Endofunctors. What is the problem?
    Costate Comonad Coalgebra is equivalent of Java's member variable update technology for haskell. Problem?
    Reply With Quote  
     

  7. #6  
    Renown Programmer

    Join Date
    Dec 2010
    Posts
    2,876
    Thanks given
    508
    Thanks received
    1,898
    Rep Power
    5000
    the wiki page practically tells you how to solve it lol
    never talk to me or my wife's son ever again
    Reply With Quote  
     

  8. Thankful users:


  9. #7  
    Registered Member
    whac's Avatar
    Join Date
    Nov 2011
    Posts
    176
    Thanks given
    35
    Thanks received
    84
    Rep Power
    245
    ty wiki for the algorithm

    Code:
    ;; Knight's tour using Warnsdorff's rule.
    ;; https://en.wikipedia.org/wiki/Knight%27s_tour
    
    (defconstant +board-sz+ 8)
    
    (defparameter *board* (make-array `(,+board-sz+ ,+board-sz+) :initial-element 0))
    
    (defconstant +knight-moves+
      '(#(1 -2) #(2 -1) #(2 1) #(1 2) #(-1 2) #(-2 1) #(-2 -1) #(-1 -2)))
    
    (defun board-at (x y)
      (aref *board* y x))
    
    (defun board-set (x y val)
      (setf (aref *board* y x) val))
    
    (defun print-board ()
      (dotimes (y +board-sz+)
        (dotimes (x +board-sz+)
          (format t "[~d] " (board-at x y))) (terpri)))
    
    (defun is-valid-sq (x y)
      (and (>= x 0) (>= y 0) (< x +board-sz+) (< y +board-sz+) (zerop (board-at x y))))
    
    (defun get-moves (x y)
      (remove-if-not (lambda (lst)
                       (apply #'is-valid-sq lst))
                     (mapcar (lambda (mvmt)
                               (let ((new-x (+ x (aref mvmt 0)))
                                     (new-y (+ y (aref mvmt 1))))
                                 (list new-x new-y))) +knight-moves+)))
    
    (defun get-min-move (moves)
      (if (null moves)
          nil
          (apply #'min (mapcar (lambda (move)
                                 (length (get-moves (car move) (second move)))) moves))))
    
    (defun next-sq (x y)
      (let* ((moves (get-moves x y))
             (min-move (get-min-move moves)))
        (when (null moves)
          (return-from next-sq nil))
        (dolist (move moves)
          (when (= min-move (length (get-moves (car move) (second move))))
            (return-from next-sq move)))))
    
    (defun sq-name (x y)
      (format nil "~C~D" (code-char (+ (char-int #\a) x)) (abs (- y +board-sz+))))
    
    (defun begin-tour (x y)
      (format t "Moved to ~A~%" (sq-name x y))
      (let ((next (next-sq x y)))
        (board-set x y 1)
        (print-board)
        (when (null next)
          (format t "No more moves!~%") (quit))
        (apply #'begin-tour next)))
    
    (begin-tour 0 0)
    https://gist.github.com/wktr/7368338
    Reply With Quote  
     

  10. Thankful users:



Thread Information
Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)


User Tag List

Similar Threads

  1. Rate the Sig Above You
    By DrDiablo in forum Forum Games
    Replies: 2667
    Last Post: 06-18-2017, 09:46 PM
  2. the dark knight
    By Full Metalst in forum Showcase
    Replies: 4
    Last Post: 09-03-2013, 11:42 AM
  3. Alfred the noble knight
    By bloodshotpk in forum Literature & Language Arts
    Replies: 1
    Last Post: 10-23-2009, 09:38 PM
  4. which one of the halo sigs do u like better?
    By man777 in forum Showcase
    Replies: 0
    Last Post: 04-01-2007, 05:22 PM
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •