编码挑战：一个骑士。在棋盘上 [英] Coding challenge: a knight.on a chessboard

问题描述

今天的挑战由Jeroen Landheer提供。



编写一个程序，让骑士跳过棋盘，使其触及所有方格，但骑士可能永远不会使用同一个地方两次。起始位置应由用户给出（或者如果您不想接受用户输入，则作为随机位置提供），并且程序必须在坐标列表中计算并输出解决方案。



示例：



开始于：A1

解决方案：A1 - B3 - C5等





上周

特别提到ProgramfoX的多语言解决方案。真棒。对于获胜者而言，JörgenAndersson和Graeme之间的关系是颈部和颈部，但是我将把它送给Jörgen，希望能激发Graeme更高级的精神错乱。

解决方案

这是一个使用Warnsdorff算法解释的解决方案：骑士之旅 - 维基百科 [ ^ ]



更新：代码经过重构而不会牺牲性能。

目标

灵活的核心，具有以下目标：



1.重复使用其他面向董事会的谜题，例如：八个女王之谜 - 维基百科 [ ^ ]，Rook polyno mial - 维基百科 [ ^ ]和 No-in-line problem - Wikipedia [ ^ ]。



2。加上其他奖金任务，如：

2a。确定给定电路板尺寸的所有可解决的巡回演出

2b。使用有效的解决方案确定最小的电路板尺寸

2c。决斗骑士 - 板上有一个或多个骑士的可解决方案。

2d。用户可以通过巡视直观地向前和向后导航，看看决策过程的工作方式，而不仅仅是正在进行的动作。

2e。性能 - 不牺牲性能的灵活性



为了满足上述所有目标，我选择使用 Stack（T）Class（System.Collections.Generic） [ ^ ]。

核心代码

代码是PCL（便携式类库）中的自包含。



为了达到性能目标，当初始化 Knight 类时，它将重置棋盘并为每个位置预先计算移动。



1. 位置类：

<前lang =C＃> 公共 < span class =code-keyword> class 位置 // 骑士的行动
{
public 位置（ int cols， int 行， int index）
{
this .cols = cols;
this .rows = rows;
this .index = index;
}

public 位置（ int cols， int 行， int index， int moveNum）
：此（cols，rows，index）
{
此。 moveNum = moveNum;
}

int cols，rows，iRow，col，row，index，moveNum;

public int MoveNum = > moveNum;

public int Index = > 指数;

public int Col
{
get
{
if （col == 0 ）calcCoords（）;
return col;
}
}

public int 行
{
get
{
if （row = = 0 ）calcCoords（）;
返回行;
}
}

私人 void calccoords（ ）
{
col = index％cols;
row = index / cols;
iRow = rows - row;
}

public 覆盖 string ToString（）
{
if （col == 0 ）calcCoords（）;
if （col < 26 ） return

{（char）（col％26 +'A'）} - {iRow};
if （col < 52 ） return

{new string（'A'，col / 26）+（char）（col％26 +'A'）} - {iRow};
return

Today's challenge is provided by Jeroen Landheer.

Write a program that lets a knight hop over a chessboard so it touches all squares, but that knight may never use the same spot twice. Starting position should be given by the user (or provided as a random location if you don't feel like accepting user input), and the program must compute and output the solution in a list of coordinates.

Example:

Start at: A1
Solution: A1 – B3 – C5 etc


Last week
Special mention to ProgramFOX for his polyglot solution. Awesome. For the winner it was neck and neck between Jörgen Andersson and Graeme but I'm going to give it to Jörgen in the hope of inspiring Graeme to even higher feats of insanity.

解决方案

Here is a solution using an interpretation of Warnsdorff’s Algorithm: Knight's tour - Wikipedia[^]

Update: the code was refactored without sacrificing performance.

Objective

Flexible core with the following goals:

1. Reuse in other board-orientated puzzles like: Eight queens puzzle - Wikipedia[^], Rook polynomial - Wikipedia[^], and No-three-in-line problem - Wikipedia[^].

2. Plus other "bonus" tasks like:
2a. Determine all solvable tours for a given board size
2b. Determine the smallest board size with a valid solution
2c. Duelling Knights - solvable solutions with one or more knights on the board.
2d. The user can visually navigate forwards and backwards through the tour and see the how the decision making process works, not just the moves being made.
2e. Performance - not sacrifice flexibility over performance

To meet all of the above objectives, I chose to work with the Stack(T) Class (System.Collections.Generic)[^].

Core Code

The code is self-contained in a PCL (portable class library).

To meet the performance goal, when the Knight class is initialized, it will reset the board and pre-calculate moves for every position.

1. Location class:

public class Location // a Knight's move
{
    public Location(int cols, int rows, int index)
    {
        this.cols = cols;
        this.rows = rows;
        this.index = index;
    }

    public Location(int cols, int rows, int index, int moveNum)
        : this(cols, rows, index)
    {
        this.moveNum = moveNum;
    }

    int cols, rows, iRow, col, row, index, moveNum;

    public int MoveNum => moveNum;

    public int Index => index;

    public int Col
    {
        get
        {
            if (col == 0) calcCoords();
            return col;
        }
    }

    public int Row
    {
        get
        {
            if (row == 0) calcCoords();
            return row;
        }
    }

    private void calcCoords()
    {
        col = index % cols;
        row = index / cols;
        iRow = rows - row;
    }

    public override string ToString()
    {
        if (col == 0) calcCoords();
        if (col < 26) return

"{(char)(col % 26 + 'A')}-{iRow}"; if (col < 52) return

"{new string('A', col / 26) + (char)(col % 26 + 'A')}-{iRow}"; return

这篇关于编码挑战：一个骑士。在棋盘上的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！