How to resolve the algorithm Solve a Hidato puzzle step by step in the C# programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Solve a Hidato puzzle step by step in the C# programming language
Table of Contents
Problem Statement
The task is to write a program which solves Hidato (aka Hidoku) puzzles. The rules are: For example the following problem has the following solution, with path marked on it:
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Solve a Hidato puzzle step by step in the C# programming language
The provided code is a solver for Hidato puzzles in C#. Hidato is a logic puzzle where the goal is to fill in a grid with numbers from 1 to the total number of cells, such that each number appears only once in each row, column, and 3x3 block.
The code is structured as follows:
-
Main Method: The
Mainmethod is the entry point of the program. It creates an instance of theSolverclass and calls theSolvemethod to solve a Hidato puzzle. -
Solver Class: The
Solverclass contains the logic to solve Hidato puzzles. It has the following methods:- Constructor: The constructor takes an array of move directions and initializes the
movesfield with these directions. - Solve (bool, string[]): This method takes a boolean value indicating whether the puzzle is circular (meaning the last number wraps around to the first) and an array of strings representing the puzzle grid. It parses the grid, initializes the
board,given, andcountfields, and then calls theSolvemethod with these parameters. - Solve (bool, int[,]): This method takes a boolean value indicating whether the puzzle is circular and a 2D array representing the puzzle grid. It parses the grid, initializes the
board,given, andcountfields, and then calls theSolvemethod with these parameters. - Solve (int[,], BitArray, int, bool): This method is the main recursive solver. It takes a 2D array representing the puzzle grid, a
BitArrayindicating which numbers are given in the puzzle, the total number of cells in the puzzle, a boolean value indicating whether the puzzle is circular, and the current position and number. It tries to fill in the current cell with the next number in sequence and recursively calls itself for each possible move direction. If a solution is found, it returnstrue, otherwise it returnsfalse. - Parse (string[]): This method parses a Hidato puzzle from an array of strings representing the puzzle grid. It initializes the
board,given, andcountfields with the parsed data. - Parse (int[,]): This method parses a Hidato puzzle from a 2D array representing the puzzle grid. It initializes the
board,given, andcountfields with the parsed data. - Scan (int[,], int, int, int): This method scans the puzzle grid to determine which numbers are given.
- Print (int[,]): This method prints the solved puzzle grid to the console.
- Constructor: The constructor takes an array of move directions and initializes the
-
Utility Methods: The following utility methods are used by the
Solverclass:- AreNeighbors: This method checks whether two positions are neighbors in the puzzle grid.
- Range (int, int): This method returns a range of integers from the first parameter to the second parameter.
The provided code is a compact and efficient implementation of a Hidato puzzle solver in C#. It uses a recursive backtracking algorithm to find a solution to the puzzle.
Source code in the csharp programming language
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
hidatoMoves = {(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)};
private (int dx, int dy)[] moves;
public static void Main()
{
Print(new Solver(hidatoMoves).Solve(false, new [,] {
{ 0, 33, 35, 0, 0, -1, -1, -1 },
{ 0, 0, 24, 22, 0, -1, -1, -1 },
{ 0, 0, 0, 21, 0, 0, -1, -1 },
{ 0, 26, 0, 13, 40, 11, -1, -1 },
{ 27, 0, 0, 0, 9, 0, 1, -1 },
{ -1, -1, 0, 0, 18, 0, 0, -1 },
{ -1, -1, -1, -1, 0, 7, 0, 0 },
{ -1, -1, -1, -1, -1, -1, 5, 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();
}
}
You may also check:How to resolve the algorithm Prime triangle step by step in the Java programming language
You may also check:How to resolve the algorithm 24 game step by step in the Bracmat programming language
You may also check:How to resolve the algorithm Evolutionary algorithm step by step in the Insitux programming language
You may also check:How to resolve the algorithm Metaprogramming step by step in the Shen programming language
You may also check:How to resolve the algorithm Greatest common divisor step by step in the Fermat programming language