Solve a Holy Knight's tour: Difference between revisions
Added C#
(Added C#) |
|||
Line 756:
24 22
43 45
</pre>
=={{header|C sharp}}==
The same solver can solve Hidato, Holy Knight's Tour, Hopido and Numbrix puzzles.<br/>
The input can be an array of strings if each cell is one character. Any non-numeric value indicates a no-go.<br/>
If there are cells that require more characters, then a 2-dimensional array of ints must be used. Any number < 0 indicates a no-go.<br/>
The puzzle can be made circular (the end cell must connect to the start cell). In that case, no start cell needs to be given.
<lang csharp>using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;
using static System.Linq.Enumerable;
public class Solver
{
private static readonly (int dx, int dy)[]
//other puzzle types elided
knightMoves = {(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1),(-2,-1),(-1,-2)};
private (int dx, int dy)[] moves;
public static void Main()
{
var knightSolver = new Solver(knightMoves);
Print(knightSolver.Solve(true,
".000....",
".0.00...",
".0000000",
"000..0.0",
"0.0..000",
"1000000.",
"..00.0..",
"...000.."));
Print(knightSolver.Solve(true,
".....0.0.....",
".....0.0.....",
"....00000....",
".....000.....",
"..0..0.0..0..",
"00000...00000",
"..00.....00..",
"00000...00000",
"..0..0.0..0..",
".....000.....",
"....00000....",
".....0.0.....",
".....0.0....."
));
}
public Solver(params (int dx, int dy)[] moves) => this.moves = moves;
public int[,] Solve(bool circular, params string[] puzzle)
{
var (board, given, count) = Parse(puzzle);
return Solve(board, given, count, circular);
}
public int[,] Solve(bool circular, int[,] puzzle)
{
var (board, given, count) = Parse(puzzle);
return Solve(board, given, count, circular);
}
private int[,] Solve(int[,] board, BitArray given, int count, bool circular)
{
var (height, width) = (board.GetLength(0), board.GetLength(1));
bool solved = false;
for (int x = 0; x < height && !solved; x++) {
solved = Range(0, width).Any(y => Solve(board, given, circular, (height, width), (x, y), count, (x, y), 1));
if (solved) return board;
}
return null;
}
private bool Solve(int[,] board, BitArray given, bool circular,
(int h, int w) size, (int x, int y) start, int last, (int x, int y) current, int n)
{
var (x, y) = current;
if (x < 0 || x >= size.h || y < 0 || y >= size.w) return false;
if (board[x, y] < 0) return false;
if (given[n - 1]) {
if (board[x, y] != n) return false;
} else if (board[x, y] > 0) return false;
board[x, y] = n;
if (n == last) {
if (!circular || AreNeighbors(start, current)) return true;
}
for (int i = 0; i < moves.Length; i++) {
var move = moves[i];
if (Solve(board, given, circular, size, start, last, (x + move.dx, y + move.dy), n + 1)) return true;
}
if (!given[n - 1]) board[x, y] = 0;
return false;
bool AreNeighbors((int x, int y) p1, (int x, int y) p2) => moves.Any(m => (p2.x + m.dx, p2.y + m.dy).Equals(p1));
}
private static (int[,] board, BitArray given, int count) Parse(string[] input)
{
(int height, int width) = (input.Length, input[0].Length);
int[,] board = new int[height, width];
int count = 0;
for (int x = 0; x < height; x++) {
string line = input[x];
for (int y = 0; y < width; y++) {
board[x, y] = y < line.Length && char.IsDigit(line[y]) ? line[y] - '0' : -1;
if (board[x, y] >= 0) count++;
}
}
BitArray given = Scan(board, count, height, width);
return (board, given, count);
}
private static (int[,] board, BitArray given, int count) Parse(int[,] input)
{
(int height, int width) = (input.GetLength(0), input.GetLength(1));
int[,] board = new int[height, width];
int count = 0;
for (int x = 0; x < height; x++)
for (int y = 0; y < width; y++)
if ((board[x, y] = input[x, y]) >= 0) count++;
BitArray given = Scan(board, count, height, width);
return (board, given, count);
}
private static BitArray Scan(int[,] board, int count, int height, int width)
{
var given = new BitArray(count + 1);
for (int x = 0; x < height; x++)
for (int y = 0; y < width; y++)
if (board[x, y] > 0) given[board[x, y] - 1] = true;
return given;
}
private static void Print(int[,] board)
{
if (board == null) {
WriteLine("No solution");
} else {
int w = board.Cast<int>().Where(i => i > 0).Max(i => (int?)Ceiling(Log10(i+1))) ?? 1;
string e = new string('-', w);
foreach (int x in Range(0, board.GetLength(0)))
WriteLine(string.Join(" ", Range(0, board.GetLength(1))
.Select(y => board[x, y] < 0 ? e : board[x, y].ToString().PadLeft(w, ' '))));
}
WriteLine();
}
}</lang>
{{out}}
<pre>
-- 23 32 21 -- -- -- --
-- 16 -- 24 31 -- -- --
-- 33 22 15 20 25 30 27
17 36 19 -- -- 28 -- 8
34 -- 14 -- -- 9 26 29
1 18 35 10 13 4 7 --
-- -- 2 5 -- 11 -- --
-- -- -- 12 3 6 -- --
-- -- -- -- -- 1 -- 37 -- -- -- -- --
-- -- -- -- -- 34 -- 56 -- -- -- -- --
-- -- -- -- 2 55 38 33 36 -- -- -- --
-- -- -- -- -- 32 35 54 -- -- -- -- --
-- -- 28 -- -- 3 -- 39 -- -- 48 -- --
29 6 25 4 31 -- -- -- 53 40 51 42 47
-- -- 30 27 -- -- -- -- -- 49 46 -- --
7 26 5 24 9 -- -- -- 45 52 41 50 43
-- -- 8 -- -- 23 -- 15 -- -- 44 -- --
-- -- -- -- -- 10 19 22 -- -- -- -- --
-- -- -- -- 18 21 16 11 14 -- -- -- --
-- -- -- -- -- 12 -- 20 -- -- -- -- --
-- -- -- -- -- 17 -- 13 -- -- -- -- --
</pre>
| |||