• Ic (unregistered)

    My Knight's Tour in perl. Just another brute-force solution.

    #!/usr/bin/perl
use strict;
use warnings;

my $cls = qx(clear);

print 'Size of board: ';
my $size = <STDIN>;
chomp $size;
my $tomove = $size**2;
my $asize  = $size - 1;

my $board = [map [map 0, 0 .. $asize], 0 .. $asize];

#<<<
my @moves = (
                [-2,-1],        [-2, 1],
        [-1,-2],                        [-1, 2],
                        ##HERE##
        [ 1,-2],                        [ 1, 2],
                [ 2,-1],        [ 2, 1]
            );
#>>>
my $start_m   = int(rand($size));
my $start_n   = int(rand($size));
my @positions = ([$start_m, $start_n]);
$board->[$start_m]->[$start_n] = -1;
my @movements = (-1);

board_print();

while ($#movements < $tomove) {
    $movements[-1]++;
    if ($movements[-1] > $#moves) {
        pop @movements;
        my $cpos = pop @positions;
        $board->[$cpos->[0]]->[$cpos->[1]] = 0;
    } else {
        my $next_m = $positions[-1]->[0] + $moves[$movements[-1]]->[0];
        my $next_n = $positions[-1]->[1] + $moves[$movements[-1]]->[1];

        if (
            !(
                   ($next_m < 0)
                || ($next_m > $asize)
                || ($next_n < 0)
                || ($next_n > $asize)
            )
          )
        {
            if (
                ($board->[$next_m]->[$next_n] == 0)
                || (($#movements == ($tomove - 1))
                    && $board->[$next_m]->[$next_n] == -1)
              )
            {
                $board->[$next_m]->[$next_n] = 1;
                push @positions, [$next_m, $next_n];
                push @movements, -1;
            }

#            print $cls;
#            board_print($board);
#            print join(' ', @movements), $/;

        }
    }

    if (!@movements) {
        print "Tour not possible on ${size}x${size} board!";
        exit 1;
    }
}

printf "Startposition: %2d:%2d\n" . "Endposition:   %2d:%2d\n",
  @{$positions[0]}, @{$positions[-1]};
print 'Movements: ', join(' ', @movements), "\n";
print "Positions:\n", join(' -> ', map { "[$_->[0],$_->[1]]" } @positions),
  "\n";
board_print($board);

print 'Press <ENTER> to start playback: ';
my $ret = <STDIN>;

my $simboard = [map [map 0, 0 .. $asize], 0 .. $asize];
for (0 .. $#positions) {
    $simboard->[$positions[$_]->[0]]->[$positions[$_]->[1]] = 1;
    print $cls;
    board_print($simboard, $_);
    print "Move: $_\n";
    sleep 1;
}

sub board_print {
    my $_board = shift;
    my $_pos   = shift;
    if (!defined $_pos) {
        $_pos = -1;
    }
    for my $m (0 .. $asize) {
        for my $n (0 .. $asize) {
            if (   ($m == $positions[$_pos]->[0])
                && ($n == $positions[$_pos]->[1]))
            {
                print 'R';
            } elsif (($m == $positions[0]->[0])
                && ($n == $positions[0]->[1]))
            {
                print 'S';
            } else {
                print $_board->[$m]->[$n] ? 'X' : '.';
            }
        }
        print "\n";
    }
}
  • Bim Job (unregistered)

    I wonder what the purpose of "Programmers' Praxis" might be?

    It's an interesting question, I think. Given that the problem in question is mathematically solvable, why not just provide the mathematical solution (as some have)?

    Assuming that the solution is available on the Web (which it invariably is), one would have thought that the "winner(s)" would provide a link and (preferably) a commentary on why the web-provided solution (a) doesn't compile (b) is sub-optimal and/or (c) is incorrect.

    Posting gobbet upon gobbet of awful instant code in random languages is surely a sign of severe autism.

    What, I think, the concept needs is a lack of refinement.

    How about this? Post an insoluble problem, and ask for a programmatic solution. It doesn't have to be the right solution (although an annoying number of posters can't even manage that for a solved problem); just an interesting solution.

    Travelling salesmen? Packing randomly-sized cuboids into a box? Anything.

    Just, please, not this. It's getting fucking irritating.

    PS Your Robot-Fu is dying. Maybe the next Programmer Praxis?

  • Bim Job (unregistered) in reply to SCB
    SCB:
    AlpineR:
    I have an original programming praxis if you want:

    No-Touch Mosaics

    Form a rectangular mosaic from square, colored pieces. Any number of pieces and any number of colors are allowed.

    Form another rectangular mosaic from the same set of pieces. But this time, don't allow any pieces that touched before to touch again. Pieces of a common color are considered interchangeable, so if a red piece touched a blue piece in the first mosaic then no red pieces can touch any blue pieces in the second mosaic. Furthermore, if two blue pieces touched in the first mosaic then no blue pieces can touch in the second mosaic.

    1. Provide an example of a pair of mosaics satisfying these rules.
    2. What is the smallest pair of mosaics (of any shape) that satisfies the rules?
    3. What is the smallest pair of square mosaics that satisfies the rules.
    4. What is the fewest number of colors necessary to form such a pair?
    5. Provide an example of the smallest pair using the fewest number of colors?

    Addendum (2009-08-12 20:37): One more rule I forgot to mention: Consider any piece on an outer edge to be in contact with all other pieces on an outer edge in the same mosaic. So if both a red piece and a blue piece are on the outer edge in the first mosaic, neither a red piece nor a blue piece can be on the outer edge in the second mosaic, nor can they touch each other in the second mosaic.

    Surely the minimal solution is just one piece.

    Fuck me, you people are idiots. That doesn't work for rules 3 and 4.
  • Thought, the hungry troll (unregistered) in reply to Bim Job
    Bim Job:
    SCB:
    AlpineR:
    I have an original programming praxis if you want:

    No-Touch Mosaics

    Form a rectangular mosaic from square, colored pieces. Any number of pieces and any number of colors are allowed.

    Form another rectangular mosaic from the same set of pieces. But this time, don't allow any pieces that touched before to touch again. Pieces of a common color are considered interchangeable, so if a red piece touched a blue piece in the first mosaic then no red pieces can touch any blue pieces in the second mosaic. Furthermore, if two blue pieces touched in the first mosaic then no blue pieces can touch in the second mosaic.

    1. Provide an example of a pair of mosaics satisfying these rules.
    2. What is the smallest pair of mosaics (of any shape) that satisfies the rules?
    3. What is the smallest pair of square mosaics that satisfies the rules.
    4. What is the fewest number of colors necessary to form such a pair?
    5. Provide an example of the smallest pair using the fewest number of colors?

    Addendum (2009-08-12 20:37): One more rule I forgot to mention: Consider any piece on an outer edge to be in contact with all other pieces on an outer edge in the same mosaic. So if both a red piece and a blue piece are on the outer edge in the first mosaic, neither a red piece nor a blue piece can be on the outer edge in the second mosaic, nor can they touch each other in the second mosaic.

    Surely the minimal solution is just one piece.

    Fuck me, you people are idiots. That doesn't work for rules 3 and 4.

    Hmm. Thot tinks Bim Job not be funny fuck. Not want.

  • jay (unregistered) in reply to Bim Job
    Bim Job:
    I wonder what the purpose of "Programmers' Praxis" might be?

    It's an interesting question, I think. Given that the problem in question is mathematically solvable, why not just provide the mathematical solution (as some have)?

    Assuming that the solution is available on the Web (which it invariably is), one would have thought that the "winner(s)" would provide a link and (preferably) a commentary on why the web-provided solution (a) doesn't compile (b) is sub-optimal and/or (c) is incorrect.

    Posting gobbet upon gobbet of awful instant code in random languages is surely a sign of severe autism.

    What, I think, the concept needs is a lack of refinement.

    How about this? Post an insoluble problem, and ask for a programmatic solution. It doesn't have to be the right solution (although an annoying number of posters can't even manage that for a solved problem); just an interesting solution.

    Travelling salesmen? Packing randomly-sized cuboids into a box? Anything.

    Just, please, not this. It's getting fucking irritating.

    PS Your Robot-Fu is dying. Maybe the next Programmer Praxis?

    I had the crazy idea that the purpose was to practice programming. Perhaps to try to come up with particularly elegant, clever, or efficient ways to solve a problem. Or perhaps simply to try out a language you haven't used before. Looking up someone else's solution doesn't accomplish any of that. Not to mention, is pretty boring, unless they're solution is particularly interesting in some way.

    Hey, I'll let you in on a secret: Have you ever done a crossword puzzle? Did you know that the person who created the crossword puzzle ALREADY HAS A SOLUTION? Did you ever take a test in school? Did you know that the teacher ALREADY KNOWS THE RIGHT ANSWERS?

  • Anonymous (unregistered) in reply to jay
    jay:
    Bim Job:
    I wonder what the purpose of "Programmers' Praxis" might be?

    It's an interesting question, I think. Given that the problem in question is mathematically solvable, why not just provide the mathematical solution (as some have)?

    Assuming that the solution is available on the Web (which it invariably is), one would have thought that the "winner(s)" would provide a link and (preferably) a commentary on why the web-provided solution (a) doesn't compile (b) is sub-optimal and/or (c) is incorrect.

    Posting gobbet upon gobbet of awful instant code in random languages is surely a sign of severe autism.

    What, I think, the concept needs is a lack of refinement.

    How about this? Post an insoluble problem, and ask for a programmatic solution. It doesn't have to be the right solution (although an annoying number of posters can't even manage that for a solved problem); just an interesting solution.

    Travelling salesmen? Packing randomly-sized cuboids into a box? Anything.

    Just, please, not this. It's getting fucking irritating.

    PS Your Robot-Fu is dying. Maybe the next Programmer Praxis?

    I had the crazy idea that the purpose was to practice programming. Perhaps to try to come up with particularly elegant, clever, or efficient ways to solve a problem. Or perhaps simply to try out a language you haven't used before. Looking up someone else's solution doesn't accomplish any of that. Not to mention, is pretty boring, unless they're solution is particularly interesting in some way.

    Hey, I'll let you in on a secret: Have you ever done a crossword puzzle? Did you know that the person who created the crossword puzzle ALREADY HAS A SOLUTION? Did you ever take a test in school? Did you know that the teacher ALREADY KNOWS THE RIGHT ANSWERS?

    If everyone took your attitude we'd still be living in caves and catching food with pointy sticks.
  • duis (unregistered) in reply to jay
    jay:
    Did you know that the teacher ALREADY KNOWS THE RIGHT ANSWERS?

    Well... Sometimes you need to show the teachers that the answers they know are wrong.

  • (cs) in reply to mark
    mark:
    curtmack:
    .... almost as disappointing as when you get your PB&J sandwich and the peanut butter is on top of the jelly ....

    mate, its a sandwich. Both are between the pieces of bread. If the 'jelly' is on top, you have it upside down.

    I was talking about how the given starting point would actually be listed as the ending point. Of course, since it's a path, it can be turned around, hence the sandwich analogy.

    A cleverer individual might have noticed that without assistance.

  • H2 (unregistered)

    Hi.

    This was a really nice task! A bit harder this time, but solvable. Here is my recursive Perl-approach, including a manual switch for the hard or easy condition (starting field == ending field ?).

    #/usr/bin/perl
use strict;
use warnings;
use Storable qw(dclone);

use constant TRUE => 1;
use constant FALSE => 0;
use constant INTERN => -1;

if ((@ARGV != 2) || ($ARGV[0]!~m/^[1-9]*x[1-9]*$/) || ($ARGV[1]!~m/^[1-9]*x[1-9]*$/)) {
	print "Missing or wrong arguments! Need two integers\n";
	exit(0);
}

my ($field_lenght,$field_height)=split('x',$ARGV[0]);
my ($start_x,$start_y)=split('x',$ARGV[1]);
if ($start_x>$field_lenght or $start_y>$field_height) {
	print "Starting position out of boundarys!\n";
	exit(0);
}

my $fields=$field_lenght*$field_height;
my @chessboard;

for (my $i=0;$i<$field_lenght;$i++) {
	for (my $j=0;$j<$field_height;$j++) {
		$chessboard[$i]->[$j]=0;
	}
}

my $moves_made=0;
my $solution;
my $result=make_move($start_x-1,$start_y-1,\@chessboard,$moves_made,\$solution);
if ($result==TRUE) {
	print "Solution found:\n";
	foreach (@$solution) {
		foreach (@{$_}) {
			print $_."\t";
		}
		print "\n\n";
	}
}
else {
	print "No solution :(\n";
}

sub make_move {
	my $pos_x=shift;
	my $pos_y=shift;
	my $chessboard=shift;
	my @chessboard=@{dclone($chessboard)};
	my $moves_done=shift;
	my $solution=shift;
	
	$moves_done++;
	$chessboard[$pos_x]->[$pos_y]=$moves_done;
	
	my @target_fields;
	my $result=locate_free_field($pos_x,$pos_y,\@chessboard,$moves_done,\@target_fields);
	
	if ($result==INTERN) {
		$$solution=\@chessboard;
		return TRUE;
	}
	elsif ($result==FALSE) {
		return FALSE;
	}
	else {
		foreach (@target_fields) {
			$result=make_move($_->[0],$_->[1],\@chessboard,$moves_done,\$$solution);
			if ($result==TRUE) {
				return TRUE;
			}
		}
		return FALSE;
	}
}

sub locate_free_field {
	my $pos_x=shift;
	my $pos_y=shift;
	my $chessboard=shift;
	my @chessboard=@$chessboard;
	my $moves_done=shift;
	my $return=shift;
	
	my @operations=([+2,+1],[+2,-1],[+1,+2],[+1,-2],[-1,+2],[-1,-2],[-2,+1],[-2,-1]);
	foreach (@operations) {
		my $new_x=$pos_x+($_->[0]);
		my $new_y=$pos_y+($_->[1]);
		if ($new_x>=0 and $new_x<$field_lenght and $new_y>=0 and $new_y<$field_height) {
			if ($chessboard[$new_x]->[$new_y]==0) {
				push @{$return},[$new_x,$new_y];
			}
			#elsif ($moves_done==$fields and $chessboard[$new_x]->[$new_y]==1)	{		# last field? hard way
			elsif ($moves_done==$fields)	{							# last field? easy way
				return INTERN;
			}
		}
	}
	
	if (@$return) {
		return TRUE;
	}
	else {
		return FALSE;
	}
}

    Greetings H2

  • Anonymous (unregistered)

    #!perl

    use strict; use Net::Amazon::MechanicalTurk;

    my ($x, $pos) = @ARGV;

    my $mturk = Net::Amazon::MechanicalTurk->new( serviceUrl => 'http://mechanicalturk.sandbox.amazonaws.com/?Service=AWSMechanicalTurkRequester', serviceVersion => '2007-06-21', accessKey => '1AAAAA1A1AAAAA11AA11', secretKey => '1aAaAAAAAAAA+aAaAaaaaaaAAA/AAAAAA1a1aAaa' );

    my $question = "Solve the Knight's Tour problem for a grid of $x by $x starting at position $pos";

    my $questionXml = <<END_XML;
<?xml version="1.0" encoding="UTF-8"?>
<QuestionForm xmlns="http://mechanicalturk.amazonaws.com/AWSMechanicalTurkDataSchemas/2005-10-01/QuestionForm.xsd">
  <Question>
    <QuestionIdentifier>1</QuestionIdentifier>
    <QuestionContent>
      <Text>$question</Text>
    </QuestionContent>
    <AnswerSpecification>
      <FreeTextAnswer/>
    </AnswerSpecification>
  </Question>
</QuestionForm>
END_XML

my $result = $mturk->CreateHIT(
    Title       => 'Knight\'s Tour',
    Description => 'Love chess?  This is for you!',
    Keywords    => 'chess, knight, tour',
    Reward => {
        CurrencyCode => 'USD',
        Amount       => 0.01
    },
    RequesterAnnotation         => 'KT',
    AssignmentDurationInSeconds => 60 * 60,
    AutoApprovalDelayInSeconds  => 60 * 60 * 10,
    MaxAssignments              => 1,
    LifetimeInSeconds           => 60 * 60,
    Question                    => $questionXml
);

my $hits = $mturk->GetReviewableHITsAll;
while (my $hit = $hits->next) {
    my $hitId = $hit->{HITId}[0];
    my $assignments = $mturk->GetAssignmentsForHITAll(
        HITId => $hitId,
        AssignmentStatus => 'Submitted'
    );
    while (my $assignment = $assignments->next) {
        my $assignmentId = $assignment->{AssignmentId}[0];
        $mturk->ApproveAssignment( AssignmentId => $assignmentId );
    }
}
  • (cs)

    This is my implementation in Java...

    package org.brainteaser;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
 * This class is intended to solve the Knights Tour problem in java using Warnsdorff's algorithm
 *
 * @author Kai Hackemesser
 */
public class KnightsTour
{

  private static final int[][] VALID_JUMPS =
      new int[][]{ { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 },
          { -2, -1 } };

  /**
   * the length of each side of the board
   */
  private final int size;

  /**
   * @param size
   *          length and with of the chess board
   */
  public KnightsTour(int size)
  {
    this.size = size;
  }

  /**
   * Start the program using one parameter or three parameters. the first parameter is the size of
   * the chessboard (a square board) optional second and third parameter define the start position,
   * if left out a random position will be selected. Parameters are 1-based, so possible positions
   * on an 6x6 field would be between (1,1) and (6,6)
   *
   * @param args
   */
  public static void main(String[] args)
  {
    int size = 0;
    if (args.length == 0)
    {
      System.out.println("missing size parameter.");
      return;
    }

    try
    {
      size = Integer.parseInt(args[0]);
      if((size & 1) == 1) {
        System.out.println("There is no way to solve this with an odd number of fields.");
        return;
      }
    }
    catch (NumberFormatException e)
    {
      System.out.println("required integer parameters");
    }

    Point start = null;
    if (args.length == 1)
    {
      System.out.println("using random start positition");
      Random rnd = new Random();
      start = new Point(rnd.nextInt(size), rnd.nextInt(size));
    }
    else if (args.length != 3)
    {
      System.out.println("this needs two integers as start position");
      return;
    }
    else
    {
      try
      {
        start = new Point(Integer.parseInt(args[1]) - 1, Integer.parseInt(args[2]) - 1);
      }
      catch (NumberFormatException e)
      {
        System.out.println("required integer parameters");
        return;
      }
    }

    new KnightsTour(size).run(start);
  }

  /**
   * prepares the execution and evaluates the result
   * @param startPoint
   *          where the search begins and must end.
   */
  private void run(Point startPoint)
  {
    LinkedList<Point> trail = new LinkedList<Point>();
    trail.add(startPoint);

    List<Point> allowedEndPositions = generateOptions(trail);

    LinkedList<Point> result = doIteration(allowedEndPositions, trail);

    if (result != null && allowedEndPositions.contains(result.getLast()))
    {
      System.out.println("Perfect solution: " + printTrail(result));
    }
    else
    {
      System.out.println("No perfect solution found for starting position " + printTrail(trail));
    }
  }

  /**
   * does the jumping
   *
   * @param trail
   *          so far already jumped
   * @return a valid path or null
   */
  private LinkedList<Point> doIteration(List<Point> allowedEndPositions, LinkedList<Point> trail)
  {
    List<Point> options = generateOptions(trail);

    if (options.isEmpty() && trail.size() == size * size
        && allowedEndPositions.contains(trail.getLast()))
    {
      return trail;
    }

    for (Point nextStep : options)
    {
      trail.addLast(nextStep);
      LinkedList<Point> result = doIteration(allowedEndPositions, trail);
      if (result != null)
      {
        return result;
      }
      trail.removeLast();
    }

    return null;
  }

  /**
   * finds valid jump targets but will only return targets not jumped yet. Results are sorted ascending by the
   * number of legal jumps avaliable from the new jump destination.
   *
   * @param last
   * @return
   */
  private List<Point> generateOptions(final LinkedList<Point> trail)
  {
    List<Point> options = calculateOptions(trail);
    Collections.sort(options, new Comparator<Point>()
    {

      @Override
      public int compare(Point o1, Point o2)
      {
        trail.addLast(o1);
        int size1 = calculateOptions(trail).size();
        trail.removeLast();
        trail.addLast(o2);
        int size2 = calculateOptions(trail).size();
        trail.removeLast();

        return size1 - size2;
      }
    });
    return options;
  }

  /**
   * returns all jump targets that are legal and not yet visited.
   *
   * @param trail
   * @return
   */
  List<Point> calculateOptions(final LinkedList<Point> trail)
  {
    List<Point> options = new ArrayList<Point>(8);
    Point last = trail.getLast();
    for (int[] validJump : VALID_JUMPS)
    {
      int newX = last.x + validJump[0];
      int newY = last.y + validJump[1];
      if (newX < 0 || newX >= size || newY < 0 || newY >= size)
      {
        continue;
      }
      Point p = new Point(newX, newY);
      if (!trail.contains(p))
      {
        options.add(p);
      }
    }
    return options;
  }

  /**
   * prints all jumps in a readable format.
   *
   * @param resultTrail
   * @return
   */
  private static String printTrail(LinkedList<Point> resultTrail)
  {
    StringBuilder out = new StringBuilder();
    for (Point p : resultTrail)
    {
      if (out.length() > 0)
      {
        out.append(", ");
      }
      out.append('(').append(p.x + 1).append(", ").append(p.y + 1).append(')');
    }

    return out.toString();
  }

}

    Cheers! SF

  • KukkerMan (unregistered)

    Ugly OCaml solution using backtrack:

    let ktour n x y =
   let n2 = n * n in
   let moves = [-1, -2; 1, -2; 2, -1; 2, 1;  1, 2; -1, 2; -2, 1; -2, -1] in
   let rec backtrack steps =
      match steps with
         [] -> []
      |  head::tail ->
            if List.length steps = n2 then
               let end_x, end_y = fst head in
               let dx, dy = abs (x - end_x), abs (y - end_y) in
               if (min dx dy) = 1 && (max dx dy) = 2 then
                  steps
               else
                  backtrack tail
            else
               let (x, y), d = head in
               let rec find_dir d =
                  let nd = d + 1 in
                  if nd = 8 then
                     Back
                  else
                     let dx, dy = (List.nth moves nd) in
                     let px, py = x + dx, y + dy in
                     if px >= 0 && px < n && py >= 0 && py < n && not (List.exists (fun ((x, y), d) -> x = px && y = py) steps) then 
                        Step (nd, px, py)
                  else
                     find_dir nd
               in
               match find_dir d with
                  Back ->
                     backtrack tail
               
               |  Step (nd, nx, ny) ->
                  backtrack (((nx, ny), 0)::(((x, y), nd)::tail))
   in
   List.rev (List.map fst (backtrack [((x, y), 0)]));;
  • Alex (unregistered) 
    It was fun to do !

Here's my java version using only one board that can undo itself. I'm not using the accessibility heuristic since I didn't think about that possibility when I did my code (I don't look for an answer on wikipedia). It's slow on bigger board and i just found out that i forgot to check if starting position is the same as the finishing position.


import java.util.ArrayList;
import java.util.List;


public class Knight {

	public static void main (String args[]){
		new Knight(6);
	}
	
	public Knight(int boardSize){
		int randomX = (int) Math.round(Math.random() * (boardSize - 1));
		int randomY = (int) Math.round(Math.random() * (boardSize - 1));
		
		Coordinate startingPos = new Coordinate(randomX, randomY);
		System.out.println("Board size :" + boardSize + "x" + boardSize);
		System.out.println("Start at " + startingPos );
		
		Board board = new Board(boardSize, startingPos);
		
		long temp = System.currentTimeMillis();
		
		List<Coordinate> results = resolvePuzzle(board);
		
		if (results != null){
			for (Coordinate c : results)
				System.out.print(c + " ");
		}
		else{
			System.out.println("Not found");
		}
		
		System.out.println("\n" + (System.currentTimeMillis() - temp) + "ms");
	}
	
	
	public List<Coordinate> resolvePuzzle(Board currentBoard){
		if (currentBoard.isFinish()){
			return currentBoard.getCurrentPath();
		}

		List<Coordinate> possibleMove = currentBoard.getPossibleMove();
		
		if (possibleMove.size() == 0)
			return null;
		
		for (Coordinate c : possibleMove){
			currentBoard.move(c);
			
			List<Coordinate> results = resolvePuzzle(currentBoard);

			if (results == null){
				currentBoard.undo();
			}
			else
				return results;
			
		}
		
		return null;		
	}
	
	public class Board{
		private boolean [][] visitedBoard;
		private Coordinate currentPos = null;
		

		private List<Coordinate> knightMoves = new ArrayList<Coordinate>();
		private List<Coordinate> currentPath = new ArrayList<Coordinate>();
		
		public Board(int size, Coordinate start){
			initKnight();
			visitedBoard = new boolean [size][size];
			move(start);
		}
		
		public void initKnight(){
			knightMoves.add(new Coordinate (-1, -2));
			knightMoves.add(new Coordinate (1, -2));
			knightMoves.add(new Coordinate (2, -1));
			knightMoves.add(new Coordinate (2, 1));
			knightMoves.add(new Coordinate (1, 2));
			knightMoves.add(new Coordinate (-1, 2));
			knightMoves.add(new Coordinate (-2, 1));
			knightMoves.add(new Coordinate (-2, -1));
		}
		
		public void move (Coordinate newPos){
			currentPos = newPos;
			visitedBoard[newPos.getX()][newPos.getY()] = true;
			currentPath.add(newPos);
		}
		
		public void undo (){
			if(currentPath.size()-2 >= 0){
				visitedBoard[currentPos.getX()][currentPos.getY()] = false;
				
				Coordinate lastPos = currentPath.get(currentPath.size()-2);
				currentPath.remove(currentPath.size() -1);
				currentPos = lastPos;
			}
		}
		

		public List<Coordinate> getPossibleMove(){
			List<Coordinate> possibleMoves = new ArrayList<Coordinate>();
			
			for (Coordinate c : knightMoves){
				Coordinate futurMove = currentPos.getDelta(c);
				
				if (!isCoordinateOutOfBound(futurMove) && !visitedBoard[futurMove.getX()][futurMove.getY()]){
					possibleMoves.add(futurMove);
				}
			}
			
			return possibleMoves;
		}
		
		public List<Coordinate> getCurrentPath(){ return currentPath;}
		
		private boolean isCoordinateOutOfBound(Coordinate coor){
			return (coor.getX() < 0 || coor.getY() < 0
					|| coor.getX() >= visitedBoard.length
					|| coor.getY() >= visitedBoard[0].length);
			
		}
		
		private boolean isFinish(){
			for (boolean[] range: visitedBoard){
				for (boolean column : range){
					if (! column)
						return false;
				}
			}
			return true;
		}
	}
	
	
	public class Coordinate{
		private int X;
		private int Y;
		
		public Coordinate(int x, int y){
			X = x;
			Y = y;
		}

		public Coordinate getDelta(Coordinate move){
			return new Coordinate( getX() + move.getX(), getY() + move.getY());			
		}
		
		public int getX(){return X;}
		public int getY(){return Y;}
		
		public String toString(){
			return "(" + getX() + "," + getY() + ")";
		}

		@Override
		public int hashCode() {
			final int PRIME = 31;
			int result = 1;
			result = PRIME * result + X;
			result = PRIME * result + Y;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (getClass() != obj.getClass())
				return false;
			final Coordinate other = (Coordinate) obj;
			if (X != other.X)
				return false;
			if (Y != other.Y)
				return false;
			return true;
		}
	}
	
}
  • kramthegram (unregistered)

    Here is my python based DFS algorithm. It takes forever because of my data type choices, and the fact that it's DFS... but it gets the job done.

    class knights:
	"""DFS Knights Tour Solver"""
	def __init__(self,start_pos=[0,0],board_size=[6,6]):
		self.moves = ((2,1), (2,-1), (1,2), (1,-2), (-1,2), (-1,-2), (-2,1), (-2,-1))
		self.board_size=board_size
		self.start_pos=start_pos
		self.depth=0
	def travel(self):
		visited_list=[]
		current_pos=list(self.start_pos)
		x=self.next_move(visited_list,current_pos)
		return x
	def valid_move(self,position=[0,0],visited_list=[]):
		"""determine if move can be made"""
		#check move stays on board
		if(position[0]<self.board_size[0] and position[1]<self.board_size[1] and position[0]>-1 and position[1]>-1):
			#check position hasn't been visited
			if position in visited_list:
				return False#already been there
			else:
				return True#new spot that is valid
		else:
			return False#outside of the board
	def finished(self,visited_list):
		"""returns true if we've completed a tour"""
		#check that we've visited enough tiles
		if(len(visited_list)==(self.board_size[0]*self.board_size[1])):
			#check that last visited is start_pos
			if(visited_list[-1]==self.start_pos):
				return True
		#if it isn't finished return false
		return False
	def next_move(self,visited_list,current_pos):
		"""chooses a next move from current position"""
		self.depth=self.depth+1
		#print "d: ", self.depth
		#print visited_list
		if(self.depth>37):
			exit()
		#iterate through possible moves
		for move in self.moves:
			#print "Trying move: ",move
			#calulate move position
			next_move=[current_pos[0]+move[0],current_pos[1]+move[1]]
			#check if this move is legal
			if(self.valid_move(next_move,visited_list)):
				#add to visited
				visited_list.append(next_move)
				#are we finished?
				if(self.finished(visited_list)):
					#we're done, return list
					self.depth=self.depth-1
					return visited_list
				else:
					#try next move
					result=self.next_move(visited_list,next_move)
					if(result!=False):
						#eventualy this worked, return it
						self.depth=self.depth-1
						return result
					else:
						#this move dead ends, remove it
						visited_list.pop()
			else:
				#not a vailid move
				pass
			#we've completed trying one of the possible moves, try the next
		#drat!, no moves worked, remove this move from visited list and return False
		#print visited_list.pop()
		self.depth=self.depth-1
		return False

spos=[0,0]
bsize=[6,6]
k=knights(spos,bsize)
trav = k.travel()
if(trav!=False):
	print spos[0]+1,spos[1]+1
	for t in trav:
		print t[0]+1,t[1]+1
  • (cs) in reply to Mr.'
    Mr.':
    Mr.'; Drop Database --:
    I had a go at the 3D tour ... I tried out 1x1x2 jumps at first but couldn't find any tours for any small boards.
    I've just realised that 1x1x2 jumps can't ever work because the sum of the knight's coordinates can never change from odd to even or from even to odd. Seems really obvious now ...

    Two possible outs.

    1. change the problem to consider a "tour" to be a Hamiltonian circuit of all the squares /with the right parity./

    2. use a different 3D generalization of the knight's move (e.g., to the opposite corner of a 1 x 2 x 3 rectangular prism... or 1 x 2 x 4, perhaps.)

  • (cs) in reply to Bim Job
    Bim Job:
    Post an insoluble problem, and ask for a programmatic solution. ... Travelling salesmen? Packing randomly-sized cuboids into a box?

    You keep using that word. I dinna think it means what you think it means.

  • A1 Hilarious (unregistered) in reply to Maurits
    Maurits:
    Bim Job:
    Post an insoluble problem, and ask for a programmatic solution. ... Travelling salesmen? Packing randomly-sized cuboids into a box?

    You keep using that word. I dinna think it means what you think it means.

    You fell victim to one of the classic blunders! The most famous is never get involved in the daily wtf programmatic praxis, but only slightly less well-known is this: never go in against a Turk when chess is on the line!

  • (cs)

    This is backtracing Javascript version. Note 1] it's terribly slooooww (now I'm really happy that I didn't try to implement it on ZX Spectrum :-) ), 2] it tries to render progress, however it shows only in Opera, other browsers are too stupid to be able to render something during script run.

    <html>
<body>

    Note that it shows progress only in Opera!
    <script>

    function Board(size) {
this.size = size
this.area = new Array(size)
for (var i=0; i<size; i++) {
this.area[i] = new Array(size)
for (var j=0; j<size; j++) {
this.area[i][j] = 0
}
}
this.count = 0
this.total = size * size
this.is_full = function() {
return this.count == this.total
}
this.try_to_place = function(x, y) {
if (x < 0 || x >= size || y < 0 || y >= size) {
return false
}
if (this.area[y][x] == 0) {
++this.count
this.area[y][x] = this.count
return true
} else {
return false
}
}
this.remove = function(x, y) {
this.area[y][x] = 0
--this.count
}
this.render = function() {
var s = ""
for (var i=0; i<size; i++) {
for (var j=0; j<size; j++) {
if (this.area[i][j] < 10) s += ' '
s += this.area[i][j]
s += ' '
}
s += '\n'
}
return s
}
}
    

    function solve(size, start_x, start_y) {
    

    var board = new Board(size)

function step(x, y) {
    if (x == start_x && y == start_y && board.count > 0) {
        if (board.is_full()) {
            alert('Found!')
            return true
        } else {
            return false
        }
    }
    if (board.try_to_place(x, y)) {
        
        var out = document.getElementById('x')
        out.innerText = board.render()
        
        var r = step(x + 2, y - 1)
        if (!r) r = step(x + 2, y + 1)
        if (!r) r = step(x - 2, y - 1)
        if (!r) r = step(x - 2, y + 1)
        if (!r) r = step(x + 1, y - 2)
        if (!r) r = step(x + 1, y + 2)
        if (!r) r = step(x - 1, y - 2)
        if (!r) r = step(x - 1, y + 2)
        if (!r) board.remove(x, y)
        return r
    }        
}

step(start_x, start_y)
document.write('End')

    

    }
    

    solve(6, 0, 0)
    
</script>
</body>
</html>

    Online (not recommended if you are not using Opera).

    BTW the antispam really sucks :-)

  • (cs) in reply to Maurits
    Maurits:
    Mr.':
    Mr.'; Drop Database --:
    I had a go at the 3D tour ... I tried out 1x1x2 jumps at first but couldn't find any tours for any small boards.
    I've just realised that 1x1x2 jumps can't ever work because the sum of the knight's coordinates can never change from odd to even or from even to odd. Seems really obvious now ...

    Two possible outs.

    1. change the problem to consider a "tour" to be a Hamiltonian circuit of all the squares /with the right parity./

    2. use a different 3D generalization of the knight's move (e.g., to the opposite corner of a 1 x 2 x 3 rectangular prism... or 1 x 2 x 4, perhaps.)

    Surely the most obvious generalisation would be 0x1x2?

  • poca (unregistered) in reply to Mathematics
    Mathematics:
    hikari:
    Someone You Know:
    The traditional Knight's Tour problem does not require that the knight end on the same square from which it began, merely that it visit each of the squares once.

    On some board sizes it is possible to do a Knight's Tour that ends where it started (a "closed tour") but on others it is not.

    As I recall, any board where both dimensions are odd can't be used to complete a closed tour.

    Indeed!

    Quick proof: On an odd x odd board there are an odd number of squares.

    To complete a closed tour we must move the knight once for every square there is on the board (as he lands on each square exactly once, including the starting square which he lands on at the end of the tour).

    Finally, the colour of the square the knight lands on changes with every move (just look at the allowed moves). So, with an odd number of total moves the knight finishes the tour on the opposite colour to which he started. But to be a closed tour he must start and end on the same square, which is clearly the same colour as itself. Contradiction.

    You missed the degenerate case of a 1x1 board: there are no moves in the Knight's Tour and the knight starts and ends on the same piece.

  • poca (unregistered) in reply to AlpineR
    AlpineR:
    I have an original programming praxis if you want:

    No-Touch Mosaics

    Form a rectangular mosaic from square, colored pieces. Any number of pieces and any number of colors are allowed.

    Form another rectangular mosaic from the same set of pieces. But this time, don't allow any pieces that touched before to touch again. Pieces of a common color are considered interchangeable, so if a red piece touched a blue piece in the first mosaic then no red pieces can touch any blue pieces in the second mosaic. Furthermore, if two blue pieces touched in the first mosaic then no blue pieces can touch in the second mosaic.

    1. Provide an example of a pair of mosaics satisfying these rules.
    2. What is the smallest pair of mosaics (of any shape) that satisfies the rules?
    3. What is the smallest pair of square mosaics that satisfies the rules.
    4. What is the fewest number of colors necessary to form such a pair?
    5. Provide an example of the smallest pair using the fewest number of colors?

    Addendum (2009-08-12 20:37): One more rule I forgot to mention: Consider any piece on an outer edge to be in contact with all other pieces on an outer edge in the same mosaic. So if both a red piece and a blue piece are on the outer edge in the first mosaic, neither a red piece nor a blue piece can be on the outer edge in the second mosaic, nor can they touch each other in the second mosaic.

    1), 2), 3) and 5): Two empty mosaics; i.e no colored pieces. 4): No colors.

  • Milamber (unregistered)

    Crappy brute force depth first recursive solution in matlab. It doesn't check for closed loops however.

    KnightTour.m:

    clear all;
    

    boardSizeX = input('Board size (x):' );
boardSizeY = input('Board size (y):' );
startPosX = input('Starting position (x):');
startPosY = input('Starting position (y):');
    

    field = zeros(boardSizeX,boardSizeY);
doMove(field,startPosX,startPosY);

    doMove.m:

    function [complete] = doMove(field,posX,posY);
complete = 0;
if(posX>size(field,1)||posX<1||posY>size(field,2)||posY<1)
return;
else
if(field(posX,posY)==1)
return;
else
field(posX,posY)=1;
if(sum(sum(field))==size(field,1)*size(field,2))
complete=1;
return;
else
if(~complete&&doMove(field,posX+1,posY+2))
disp([posX,posY,iterationCount]);
complete=1;
end
if(~complete&&doMove(field,posX-1,posY+2))
disp([posX,posY,iterationCount]);
complete=1;
end
if(~complete&&doMove(field,posX-1,posY-2))
disp([posX,posY,iterationCount]);
complete=1;
end
if(~complete&&doMove(field,posX+1,posY-2))
disp([posX,posY,iterationCount]);
complete=1;
end
if(~complete&&doMove(field,posX+2,posY+1))
disp([posX,posY,iterationCount]);
complete=1;
end
if(~complete&&doMove(field,posX+2,posY-1))
disp([posX,posY,iterationCount]);
complete=1;
end
if(~complete&&doMove(field,posX-2,posY-1))
disp([posX,posY,iterationCount]);
complete=1;
end
if(~complete&&doMove(field,posX-2,posY+1))
disp([posX,posY,iterationCount]);
complete=1;
end
end
end
end
  • Minko (unregistered)

    backtracking... I must have a solution in ADA somewhere back from the early college years.

  • Silo (unregistered)

    Python solution that does brute force and the algorithm thingey on wikipedia.

    ''' Created on Aug 13, 2009

    @author: silo ''' from Numeric import zeros import random

    def possibleMoves(board, knightMoves, knightLoc): moveList = [] for move in knightMoves: newPos = (knightLoc[0] + move[0],knightLoc[1] + move[1]) if legalMove(newPos, board): moveList.append(move) return moveList

    def legalMove(newPos, board): if(newPos[0] >= 0 and newPos[1] >=0 and newPos[0] < len(board) and newPos[1] <len(board)): if(board[newPos[0]][newPos[1]] == 0): return True return False

    def performMove(move, board, knightLoc, moveCounter): newPos = (knightLoc[0] + move[0],knightLoc[1] + move[1]) board[newPos[0]][newPos[1]] = moveCounter return newPos

    def boardIsComplete(board, currentPos, startingPos, closed):

    if closed:
    if currentPos[0] != startingPos[0] or currentPos[1] != startingPos[1]:
        return False
for row in board:
    if 0 in row:
        return False
return True

    def selectMove(moveList): return moveList[random.randint(0,len(moveList)-1)]

    def completeBoard(startLoc, board, knightMoves): knightLoc = startLoc takenMoves = [] moveCounter = 2 while True: moves = possibleMoves(board, knightMoves, knightLoc) if len(moves) == 0: break move = selectMove(moves); takenMoves.append(move); knightLoc = performMove(move, board, knightLoc, moveCounter) moveCounter = moveCounter + 1 return (board, takenMoves, knightLoc)

    def useAlg(startLoc, board, knightMoves): knightLoc = startLoc takenMoves = [] moveCounter = 2 while True: moves = possibleMoves(board, knightMoves, knightLoc) if len(moves) == 0: break nMoves = 10; moveToTake = knightMoves[0] for move in moves: newNMoves = len(possibleMoves(board,knightMoves, (knightLoc[0] + move[0],knightLoc[1] + move[1]))) if newNMoves < nMoves: nMoves = newNMoves moveToTake = move takenMoves.append(moveToTake); knightLoc = performMove(moveToTake, board, knightLoc, moveCounter) moveCounter = moveCounter + 1 return (board, takenMoves, knightLoc)

    def performTour(startLoc, board, knightMoves, closed): while True: board = zeros(boardSize) board[startLoc[0]][startLoc[1]] = 1 completedBoard = completeBoard(startLoc, board, knightMoves) if boardIsComplete(completedBoard[0],completedBoard[2], startLoc, closed): break return completedBoard

    knightMoves = [(-2,1),(-2,-1),(-1,2), (-1,-2), (1,2), (1,-2), (2,1), (2,-1)] boardSize = 5,5 startLoc = (0,0) board = zeros(boardSize) board[startLoc[0]][startLoc[1]] = 1 closed = False #completedBoard = useAlg(startLoc, board, knightMoves) completedBoard = performTour(startLoc, board, knightMoves, closed)

    print completedBoard[0] print completedBoard[1

  • Mr.'; Drop Database -- (unregistered)

    I know this is late, but I have devised an ultra-fast algorithm for this problem, based on splicing a bunch of small, hard-coded tours together. This can calculate a 1000x1000 tour in 10 seconds. It would be easy to rewrite in any language, and would parallelise well.

    def instatour(w, h):
grid = [[None] * w for y in range(h)]
deltas = [None,(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]
def rv(s): return ''.join(' 56781234'[int(c)] for c in s[::-1])
def transpose(s): return ''.join(' 21876543'[int(c)] for c in s)
def apply(x, y, s, initial=False):
for c in s:
d = ord(c) - ord('0'); dy, dx = deltas[d]
grid[y][x] = d; x += dx; y += dy
if initial: grid[y][x] = 0
def splice(p1, p2, s):
x1, y1 = p1; x2, y2 = p2
dy1, dx1 = deltas[grid[y1][x1]] or (0,0)
dy2, dx2 = deltas[grid[y2][x2]] or (0,0)
if x1 + dx1 == x2 and y1 + dy1 == y2: apply(x1, y1, s)
elif x2 + dx2 == x1 and y2 + dy2 == y1: apply(x2, y2, rv(s))
else: assert False
def hjoin(x, y, h):
p1, p2 = joiners[h]
splice((x-1,y+2), (x-2,y), p1)
if p2: splice((x-1,y+h-3), (x-2,y+h-1), p2)
def vjoin(x, y, w):
p1, p2 = joiners[w]
splice((x+2,y-1), (x,y-2), transpose(p1))
if p2: splice((x+w-3,y-1), (x+w-1,y-2), transpose(p2))
starters = [
(6,5,'18236145681316745327713457247'),
(8,5,'181245467181472354578183256458241714547'),
(6,6,'22476812361456724281675417234587835'),
(7,6,'18132583546781464238186744632835887234764'),
(8,6,'12254787143814617645416321816752745432771135457'),
(8,7,'2742316385281867527454388823258356861246438286523686538'),
(8,8,'274232818676361232583683454767818354147147442176418345888754538'),
(10,3,'27418814636418814725835525538'),
(12,3,'27418818258361454635828185358364538'),
(5,4,'2175428744186438165'),
(6,4,'27427824725836836438631'),
(7,4,'274272874275353863178247521'),
(8,4,'2742727824725635386317287452713'),
(5,5,'183254774217643186532783'),
(7,5,'1813456818325864532741611664182454'),
(4,3,'14714725835'),
(7,3,'28825836145472582581'),
(8,3,'27418825836145538814641'),
(9,3,'27418814725835541744711853'),
]
joiners = {
3: ('7147147258355',None),
4: ('712572465','287427534'),
5: ('712467134772357832565',None),
6: ('8832461478645','1167538521354'),
7: ('71471413471468683421641758645',None),
8: ('88341428538758645','11658571461241354'),
}
for startw, starth, startpath in starters:
if (startw % 4 == w % 4 and startw <= w and
starth % 4 == h % 4 and starth <= h):
break
if (startw % 4 == h % 4 and startw <= h and
starth % 4 == w % 4 and starth <= w):
startw, starth = starth, startw
startpath = transpose(startpath)
break
else: print('impossible'); return
apply(0, 0, startpath, True)
for x in range(startw, w, 4): hjoin(x, 0, starth)
for y in range(starth, h, 4): vjoin(0, y, startw)
for y in range(starth, h, 4):
for x in range(startw, w, 4):
vjoin(x, y, 4)
x = y = count = 0
global outputgrid
outputgrid = [['X'] * w for y in range(h)]
while True:
last = grid[y][x] == 0
count += 1
assert 0 <= x < w and 0 <= y < h and outputgrid[y][x] == 'X'
outputgrid[y][x] = count
if last: break
dy, dx = deltas[grid[y][x]]
x += dx; y += dy
assert count == wh
if (x,y)==(1,2) or (x,y)==(2,1): print('Tour is CLOSED')
else: print('Tour is OPEN')
colw = len(str(wh))+1
for row in outputgrid:
print(('%'+str(colw)+'i') * w % tuple(row))

  • marc (unregistered) in reply to Level 2

    Another perl solution (prints all possible tours)

    #!/usr/bin/perl -- my $boardside=6; $startx=3; $starty=3; my @board=(1..(($boardside+4)*($boardside+4)));

    sub getboardfield { my ($boardref,$x,$y)=(@_); my $board=$boardref; $len=@board; $side=sqrt($len)-4; #print "side=$side\n"; $elnum=($x+1)*($side+4)+($y+1); $retval=$board->[$elnum]; #print "elnum=$elnum, returning $retval\n"; return $retval; }

    sub setboardfield { my ($boardref,$x,$y,$val)=(@_); my $board=$boardref; $len=@board; $side=sqrt($len)-4; #print "setboardfield($x,$y,$val) of board w/size $side*$side \n"; $elnum=($x+1)*($side+4)+($y+1); #print "elnum=$elnum\n"; $board->[$elnum]=$val; }

    sub initboard { my ($boardref)=(@_); #my @board=@{$boardref}; my $board=$boardref; $len=@board; $side=sqrt($len)-2; # edges for ($i=0;$i<$len;$i++) { $board->[$i]=-1; }

    # empty fields
    for ($x=1;$x<=$side;$x++)
    {
        for ($y=1;$y<=$side;$y++)
        {
        	setboardfield($board,$x,$y,0);
    }
    }

    }

    sub printboard { my ($boardref)=(@_); my @board=@{$boardref}; print "\n"; $len=@board; $side=sqrt($len)-2; for ($x=1;$x<=$side;$x++) { for ($y=1;$y<=$side;$y++) { $v=getboardfield($boardref,$x,$y); $fieldcontent="."; if ($v>0) { $fieldcontent=$v; } printf "%02d ", $fieldcontent; } print "\n"; } }

    sub solve { my ($boardref,$currentstep,$startx,$starty,$x,$y)=(@_); #print "solve step $currentstep startx,y=$startx,$starty x,y=$x,$y\n"; my @board=@{$boardref}; if (getboardfield($boardref,$x,$y)!=0) { return; } $len=@board; $side=sqrt($len)-4; setboardfield($boardref,$x,$y,$currentstep); if ($currentstep>=(($side*$side))) { printboard($boardref); return; } solve($boardref,$currentstep+1,$startx,$starty,$x-2,$y-1); solve($boardref,$currentstep+1,$startx,$starty,$x-1,$y-2); solve($boardref,$currentstep+1,$startx,$starty,$x+1,$y-2); solve($boardref,$currentstep+1,$startx,$starty,$x+2,$y-1); solve($boardref,$currentstep+1,$startx,$starty,$x-2,$y+1); solve($boardref,$currentstep+1,$startx,$starty,$x-1,$y+2); solve($boardref,$currentstep+1,$startx,$starty,$x+1,$y+2); solve($boardref,$currentstep+1,$startx,$starty,$x+2,$y+1); setboardfield($boardref,$x,$y,0); }

    initboard(@board); $currentstep=1; $x=$startx; $y=$starty; solve(@board,$currentstep,$startx,$starty,$x,$y);

  • Mr.'; Drop Database -- (unregistered)
    [image] I rewrote my Python code in C# and added graphical output, as well as some parallelism. This program can calculate a 10000x10000 tour in 20 seconds. Seriously.

    The source code is too long to post here so I embedded it in the image. Save the image somewhere and rename it to a .rar extension to extract the files.

    The algorithm is simply to splice together a bunch of smaller, hardcoded tours.

  • (cs) in reply to Mr.'; Drop Database --
    Mr.'; Drop Database --:
    [image] I rewrote my Python code in C# and added graphical output, as well as some parallelism. This program can calculate a 10000x10000 tour in 20 seconds. Seriously.

    The source code is too long to post here so I embedded it in the image. Save the image somewhere and rename it to a .rar extension to extract the files.

    The algorithm is simply to splice together a bunch of smaller, hardcoded tours.

    Okay, that's weird. The file appears to begin with a PNG header, and has a RAR header much further down. I can understand a PNG being OK with garbage at the end, but why would RAR allow garbage at the top of the file?

    Works, though!

  • Mr.'; Drop Database -- (unregistered) in reply to Daniel Beardsmore
    Daniel Beardsmore:
    Okay, that's weird. The file appears to begin with a PNG header, and has a RAR header much further down. I can understand a PNG being OK with garbage at the end, but why would RAR allow garbage at the top of the file?

    Works, though!

    Apparently WinRAR scans the file for a RAR header for some reason. It's just a matter of:

    copy /b in.png + knightstour.rar out.png

  • Texas Jack (unregistered)

    My first Common Lisp program for ten years. If any Lispers out there can critique my program, I'd appreciate it.

    My first version was annoyingly slow, so this uses http://en.wikipedia.org/wiki/Knight%27s_tour#Warnsdorff.27s_algorithm

    Usage:

    ;;CL-USER> (knights-tour 10 2)
BOARD<
 25  50   1  54  23  48  83  44  21  46 
  2  53  24  49 100  57  22  47  64  43 
 51  26  61  58  55  84  63  82  45  20 
 60   3  52  99  62  81  56  85  42  65 
 27  76  59  80  97  90  87  66  19  40 
  4  69  98  75  88  67  92  41  86  15 
 77  28  79  68  91  96  89  16  39  18 
 70   5  72  95  74  33  36  93  14  11 
 29  78   7  34  31  94   9  12  17  38 
  6  71  30  73   8  35  32  37  10  13 
>

    (defparameter *knight-moves* `((-1 -2) (-1 2) (-2 -1) (-2 1) (1 -2) (1 2) (2 -1) (2 1)))

(defstruct (board
	     (:constructor make-board-with-dim (dim))
	     (:print-function print-board))
  dim
  (data (make-array (* dim dim) :element-type '(integer) :initial-element 0))
  (move-vector ())
  (accessibility (make-array (* dim dim) :element-type '(integer) :initial-element 0)))

(defun print-board (board &optional (stream t) (level 1))
  (let ((dim (board-dim board))
	(data (board-data board)))
    (format stream "BOARD<~&")
    (dotimes (y dim)
      (dotimes (x dim)
	(format stream "~3d " (aref data (+ (* y (board-dim board)) x))))
      (format stream "~&"))
    (format stream ">~&")))

(defun make-move-vector (board)
  (let* ((dim (board-dim board))
	 (moves (make-array (* dim dim) :initial-element nil)))
    (dotimes (y dim) 
      (dotimes (x dim)
	(let* ((pos (+ (* dim y) x))
	       (posmoves ()))
	  (dolist (rel *knight-moves*)
	    (let* ((xd (car rel))
		   (yd (cadr rel))
		   (xp (+ x xd))
		   (yp (+ y yd)))
	      (if (and (< xp dim)
		       (< yp dim)
		       (> xp -1)
		       (> yp -1))
		  (setf posmoves (cons (+ (* dim yp) xp) posmoves))))
	    (setf (aref moves pos) posmoves)))))
    (setf (board-move-vector board) moves)))

(defun make-accessibility (board)
  (let* ((dim (board-dim board)))
    (dotimes (i (* dim dim))
      (update-neighbor-accessibility board i 1))))

(defun move-to (board pos level)
  (setf (aref (board-data board) pos) level)
  (update-neighbor-accessibility board pos (if (= level 0) 1 -1)))

(defun update-neighbor-accessibility (board pos how)
  (let* ((moves (aref (board-move-vector board) pos))
	 (accessibility (board-accessibility board)))
    (mapcar #'(lambda (posp)
		(setf (aref accessibility posp)
		      (+ how (aref accessibility posp))))
	    moves)))

(defun knights-tour (dim where)
  (let ((board (make-board-with-dim dim)))
    (make-move-vector board)
    (make-accessibility board)
    (find-first-soln board where where 1 (length (board-data board)))))

(defun find-first-soln (board start where level needed)
  (if (= (aref (board-data board) where) 0)
      (let ((next-level (+ level 1))
	    (next-needed (- needed 1))
	    (moves (board-move-vector board))
	    (accessibility (board-accessibility board)))
	(move-to board where level)
	(cond ((and (= next-needed 0)
		    (some #'(lambda (final-move) (= final-move start)) (aref moves where)))
	       board)
	      ((some #'(lambda (next-where)
			 (find-first-soln board
					  start
					  next-where
					  next-level
					  next-needed))
		     (sort (copy-list (aref moves where))
			   #'(lambda (a b) (< (aref accessibility a)
					      (aref accessibility b))))))
	      (t (move-to board where 0)
		 nil)))))
  • (cs) in reply to Daniel Beardsmore
    Daniel Beardsmore:
    Okay, that's weird. The file appears to begin with a PNG header, and has a RAR header much further down. I can understand a PNG being OK with garbage at the end, but why would RAR allow garbage at the top of the file?

    Every packer I know allows that. It allows the (un)packer to open self-extracting archives, which is often useful (e.g. for extracting the self-extracting archive on a different platform, etc.)

  • (cs) in reply to Mr.'; Drop Database --

    Nice and fast, but it does not allow to set the start position. Is that limitation of that algorthm? And I noticed that for some sizes the end position is not equal the start position, I don't know if it is because such soluton does not exists for a particular size (that it should warn about it) or it just ignores this rule.

    Anyway, cool solution.

  • Mr.'; Drop Database -- (unregistered) in reply to mol1111
    mol1111:
    Nice and fast, but it does not allow to set the start position. Is that limitation of that algorthm? And I noticed that for some sizes the end position is not equal the start position, I don't know if it is because such soluton does not exists for a particular size (that it should warn about it) or it just ignores this rule.

    Anyway, cool solution.

    It returns to the starting position whenever it's possible to do so. It's impossible for any grid with an odd number of squares, for 4xN tours, and for any 3xN where N < 10. I don't see any need for a warning; you need only look at the top-left square.

    As for setting the starting point, that turns out not to have any real impact on the problem. The problem statment asks for the knight returns to its starting point: in that case, the starting point is meaningless.

  • silentStatic (unregistered)

    load "Array2";

    exception noMove

    fun addPos (x, y) (xs, ys) = (x + xs, y + ys)

    fun legalMoves [] _ = [] | legalMoves ((x, y) :: xs) n = if (x > 0 andalso x <= n) andalso (y > 0 andalso y <= n) then (x, y) :: legalMoves xs n else legalMoves xs n;

    fun testMoves [] _ _ _ _ = raise noMove | testMoves ((x, y) :: xs) matrix start size count =
    let val newMatrix = Array2.array(size, size, 0) val someSize = (SOME size) val region = {base = matrix, row = 0, col = 0, nrows = someSize, ncols = someSize} val contain = {src = region, dst = newMatrix, dst_row = 0, dst_col = 0} val test = Array2.copy contain val already = Array2.sub(newMatrix, x - 1, y - 1) val test2 = Array2.update(newMatrix, x - 1, y - 1, 1) in if already = 0 (We haven't already visited the position - so we try that path) then (x, y) :: doStep (x, y) newMatrix start size count handle noMove => testMoves xs matrix start size count (We have already visited this position, so we try another possible move) else testMoves xs matrix start size count end and doStep (x, y) matrix start size count = let val moveMod = [(1,2), (2,1), (2, ~1), (1, ~2), (~1, ~2), (~2, ~1), (~2, 1), (~1, 2)] val allMoves = map (addPos (x, y)) moveMod val moves = legalMoves allMoves size in
    if (x, y) = start andalso count = (size * size) then start :: [] else if moves = [] orelse ((x, y) = start andalso count > 0) then raise noMove else testMoves moves matrix start size (count + 1) end;

    fun knightRun size pos = let val matrix = Array2.array(size, size, 0) in if size % 2 = 0 then doStep pos matrix pos size 0 else [] end;

  • (cs) in reply to Anonymous
    Anonymous:
    Perfect coder:
    This is exactly the point I was trying to make - by copying a well-known problem off Wikipedia there is absolutely no challenge posed here; why even bother to work out an answer when thousands of people have beat you to it?

    You'll find that nearly all problems out there have been solved by thousands before, even ones you haven't heard of. It still can be a challenge - just don't Google the answer. Sit back in your chair, think about the problem, and try and solve it on your own, using what you know. THAT is the whole idea behind problem solving challenges - not who can Google a solution the fastest.

    Some people feel that posting an answer the fastest must be "winning" these challenges - it's not.

    Once again:

    why even bother to work out an answer when thousands of people have beat you to it?
    1. Because it's good mental exercise
    2. Because it should be fun
    3. Because finding a solution on your own is rewarding

    If you really want to test your intellect on unsolved problems that you can't Google and get an answer to, here's a list to get you started:

    http://mathworld.wolfram.com/UnsolvedProblems.html

  • Brad (unregistered) in reply to kramthegram
    kramthegram:
    Here is my python based DFS algorithm. It takes forever because of my data type choices, and the fact that it's DFS... but it gets the job done. 
    class knights:
	"""DFS Knights Tour Solver"""
	def __init__(self,start_pos=[0,0],board_size=[6,6]):
		self.moves = ((2,1), (2,-1), (1,2), (1,-2), (-1,2), (-1,-2), (-2,1), (-2,-1))
		self.board_size=board_size
		self.start_pos=start_pos
		self.depth=0
	def travel(self):
		visited_list=[]
		current_pos=list(self.start_pos)
		x=self.next_move(visited_list,current_pos)
		return x
	def valid_move(self,position=[0,0],visited_list=[]):
		"""determine if move can be made"""
		#check move stays on board
		if(position[0]<self.board_size[0] and position[1]<self.board_size[1] and position[0]>-1 and position[1]>-1):
			#check position hasn't been visited
			if position in visited_list:
				return False#already been there
			else:
				return True#new spot that is valid
		else:
			return False#outside of the board
	def finished(self,visited_list):
		"""returns true if we've completed a tour"""
		#check that we've visited enough tiles
		if(len(visited_list)==(self.board_size[0]*self.board_size[1])):
			#check that last visited is start_pos
			if(visited_list[-1]==self.start_pos):
				return True
		#if it isn't finished return false
		return False
	def next_move(self,visited_list,current_pos):
		"""chooses a next move from current position"""
		self.depth=self.depth+1
		#print "d: ", self.depth
		#print visited_list
		if(self.depth>37):
			exit()
		#iterate through possible moves
		for move in self.moves:
			#print "Trying move: ",move
			#calulate move position
			next_move=[current_pos[0]+move[0],current_pos[1]+move[1]]
			#check if this move is legal
			if(self.valid_move(next_move,visited_list)):
				#add to visited
				visited_list.append(next_move)
				#are we finished?
				if(self.finished(visited_list)):
					#we're done, return list
					self.depth=self.depth-1
					return visited_list
				else:
					#try next move
					result=self.next_move(visited_list,next_move)
					if(result!=False):
						#eventualy this worked, return it
						self.depth=self.depth-1
						return result
					else:
						#this move dead ends, remove it
						visited_list.pop()
			else:
				#not a vailid move
				pass
			#we've completed trying one of the possible moves, try the next
		#drat!, no moves worked, remove this move from visited list and return False
		#print visited_list.pop()
		self.depth=self.depth-1
		return False

spos=[0,0]
bsize=[6,6]
k=knights(spos,bsize)
trav = k.travel()
if(trav!=False):
	print spos[0]+1,spos[1]+1
	for t in trav:
		print t[0]+1,t[1]+1

    Can anybody please write a solution for square 4x4 and 5x5 with using DFS (depth-first algorithm) in java or C#?

  • MarsUpThePump (unregistered) in reply to Alex Papadimoulis

    How about making the board into a torus? Sphere will also do.

Leave a comment on “Automating the Knight’s Tour”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article