Binary.cs 18.11 KiB
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Windows.Forms;
namespace PuzzlePlayer_Namespace
{
/* The binair board consist of 1 and 0
* This means that the possible states a cell can be are: empty, one or zero
* To specify this in an int[,] array we will use -1 for an empty space,
* 0 for a space with a zero and 1 for a space with a one
* The empty space is a constant defined in the abstract Board class
*/
internal class Binary : Board
{
// constructor with boardSize parameter (default is set to 8 but can be changed)
public Binary(int boardSize = 6) // should be even
{
boardState = GetClearBoard(boardSize,boardSize);
lastGeneratedBoard = GetClearBoard(boardSize, boardSize);
description = "Binary puzzle is played on any even-numbered square grid, with some cells initially containing black or white circles. The goal of the puzzle is to fill all cells such that:\r\n● More than two circles of the same color cannot be adjacent\r\n● Each row and column must contain an equal number of black and white circles";
drawFactor = 8;
// clear the board (fill it in with -1)
//Clear(false);
}
public override void Draw (Graphics gr, Rectangle r) //draws board in rectangle R. warning: will stretch image unless FitBoard() is used for rectangle size
{
Size tilesize = new Size(r.Width / boardState.GetLength(0), r.Height / boardState.GetLength(1));
Pen border = new Pen(Color.Black, 2);
gr.FillRectangle(Brushes.Beige, r.X, r.Y, tilesize.Width*boardState.GetLength(0), tilesize.Height*boardState.GetLength(1));
for (int i = 0; i < boardState.GetLength(0); i++)
{
for(int j = 0; j < boardState.GetLength(1); j++)
{
gr.DrawRectangle(Pens.LightGray,
r.X+i* tilesize.Width,
r.Y+j* tilesize.Height,
tilesize.Width,
tilesize.Height);
if (boardState[i,j] == 0)
{
gr.FillEllipse(Brushes.White,
(int)(r.X + ((double)i + 0.125) * tilesize.Width),
(int)(r.Y + ((double)j + 0.125) * tilesize.Height),
tilesize.Width * 3 / 4,
tilesize.Height * 3 / 4);
gr.DrawEllipse(border,
(int)(r.X + ((double)i + 0.125) * tilesize.Width + border.Width/2),
(int)(r.Y + ((double)j + 0.125) * tilesize.Height + border.Width/2),
tilesize.Width * 3 / 4 - border.Width,
tilesize.Height * 3 / 4 - border.Width);
}
if (boardState[i, j] == 1)
{
gr.FillEllipse(Brushes.Black,
(int)(r.X + ((double)i + 0.125) * tilesize.Width),
(int)(r.Y + ((double)j + 0.125) * tilesize.Height),
tilesize.Width * 3 / 4,
tilesize.Height * 3 / 4);
}
if (lastGeneratedBoard[i,j] != Board.emptySpace)
{ gr.FillRectangle(Brushes.LightGray,
(int)(r.X + ((double)i + 0.4375) * tilesize.Width),
(int)(r.Y + ((double)j + 0.4375) * tilesize.Height),
tilesize.Width / 8,
tilesize.Height / 8);
}
}
}
}
// generates a random solvable board
public override void Generate()
{
// generate a board with a brute force methode
// this methode works fine for boards with a size of 6x6 or less. But takes exponential more time if the board size is bigger
int counter = 1;
int[,] generatedBoard;
//generates a board starting with an empty board and a empty HashSet
while ((generatedBoard = BackTrackAlgorithm(GetClearBoard(boardState.GetLength(0), boardState.GetLength(1)), new HashSet<string>())) == null)
{
counter++;
Debug.WriteLine($"board is null....trying for the {counter} time");
}
//MessageBox.Show($"Found board in {counter} tries");
boardState = (int[,])generatedBoard.Clone();
// generate a list with all positions
List<(int,int)> allPositions = new List<(int,int)> ();
for(int i = 0; i < boardState.GetLength(0); i++)
for(int j = 0; j < boardState.GetLength(1); j++)
allPositions.Add(new (i, j));
Random rnd = new Random();
//remove spaces until the board is unsolvable, then go one step back
while (true)
{
if(allPositions.Count == 0)
break;
int i = rnd.Next(allPositions.Count);
(int x, int y) = allPositions[i];
int copy = boardState[x,y]; // create a copy in case it is not possible to solve the puzzle anymore
boardState[x,y] = emptySpace;
allPositions.RemoveAt(i);
if(Solve(true) == SOLUTIONS.NONE)
{
boardState[x, y] = copy; // restore the copy if there are no solutions found
}
}
// save the generated board for testing the users solution and the use of a reset button
lastGeneratedBoard = (int[,])boardState.Clone();
}
private static void PrintBoard(int[,] board)
{
for (int i = 0; i < board.GetLength(0); i++)
{
for (int j = 0; j < board.GetLength(1); j++)
Debug.Write(board[i, j] == emptySpace ? "." : board[i, j].ToString());
Debug.WriteLine("");
}
Debug.WriteLine(new string('-', 20)); }
private static string BoardToString(int[,] board)
{
string result = "";
for (int i = 0; i < board.GetLength(0); i++)
{
for (int j = 0; j < board.GetLength(1); j++)
{
result += (board[i, j] == emptySpace ? "." : board[i, j].ToString());
}
result += "|";
}
return result;
}
private static int[,] BoardFromString(string board)
{
string[] parts = board.Split('|',StringSplitOptions.RemoveEmptyEntries);
int[,] result = new int[parts.Length, parts.Length];
for (int i = 0; i < result.GetLength(0); i++)
{
for (int j = 0; j < result.GetLength(1); j++)
{
string s = parts[i][j].ToString(); // convert char to string
if (s == ".")
result[i, j] = emptySpace;
else if (s == "1" || s == "0")
result[i, j] = int.Parse(s); // convert string to int
else
return null; //invalid input string
}
}
return result;
}
private static int recursionDepth = 0;
private static int maxDepth = 100000; // max recurtion depth that is allowed
private static int maxBoardsInHashSet = 40000;
// generates a random board with a backtracking algorithm
// After searching online about what the best way is to make a random puzzle generator a lot of people pointed towards a backtracking algorithm
// I found the information about what a backtracking algorithm is here: https://www.geeksforgeeks.org/introduction-to-backtracking-2/
// But i wrote all the code myself
// It uses a HashSet to blablalblalbllablalblablablal
private static int[,] BackTrackAlgorithm(int[,] board, HashSet<string> alreadyCheckedBoards)
{
//recursionDepth++;
if (recursionDepth > maxDepth || alreadyCheckedBoards.Count > maxBoardsInHashSet)
{
return null;
}
// print board for debugging
//PrintBoard(board);
// check if the board is complete. if so then we can return the result
if (IsBoardCompletlyFilledIn(board))
{
recursionDepth--;
return board;
}
// get all the possible choices and per choice do the backtrackAlgorithm
List<Move> choices = GetChoices(board);
// if there aren't any solutions then that could mean that the whole board is filled in, or that we are stuck and need to backtrack
// and because we already did a check if the board is completly filled-in, we know that we need to backtrack
if (choices.Count == 0)
{
recursionDepth--;
return null; // backtrack
}
// check if the current board is already imposible to complete even tho there are still choices left
if (!BoardIsPosible(board, choices))
{
recursionDepth--;
return null;
}
choices.Shuffle(); //shuffle the choices around for random results everytime
//(Shuffle methode from the extentions class in the Board.cs file
// do the algorithm for every move
foreach (Move m in choices)
{
int[,] newBoard = (int[,])board.Clone(); //create a shallow clone to avoid multiple paths refrencing the same object
newBoard[m.x, m.y] = m.changeTo;
string newBoardString = BoardToString(newBoard);
if (alreadyCheckedBoards.Contains(newBoardString))
{
recursionDepth--;
return null;
}
alreadyCheckedBoards.Add(newBoardString);
int[,] result = BackTrackAlgorithm(newBoard, alreadyCheckedBoards); // recursion for every move
if (result != null)
{
recursionDepth--;
return result;
}
}
recursionDepth--;
// if all choices fail then we should also return null
return null;
}
// checks if the board has a possible outcome to optimise the generating process
private static bool BoardIsPosible(int[,] board, List<Move> choices)
{
if (choices.Count == 0) //if there are no choices then the board is imposible
return false;
List<(int, int)> emptyLocations = new List<(int, int)>();
for (int i = 0; i < board.GetLength(0); i++)
{
for (int j = 0; j < board.GetLength(1); j++)
{
if (board[i, j] == emptySpace)
emptyLocations.Add((i, j)); //add all the empty locations to the list
}
}
// Verify each empty location has a valid move
foreach (Move move in choices)
{
if (emptyLocations.Contains((move.x, move.y)))
{
emptyLocations.Remove((move.x, move.y));
if (emptyLocations.Count == 0) // if there are none left we can return true
return true;
}
}
return emptyLocations.Count == 0; // if there are none left we can return true
}
// get all the possible choices
private static List<Move> GetChoices(int[,] board)
{
List<Move> choices = new List<Move>();
// loop for both 1 and 0
for (int checkFor = 0; checkFor <= 1; checkFor++)
{
// check foreach cell if it doesn't violate the rules
for (int i = 0; i < board.GetLength(0); i++)
for (int j = 0; j < board.GetLength(1); j++)
{
if(board[i, j] == emptySpace && !DoAllChecks(i,j,board,checkFor))
choices.Add(new Move(i, j, checkFor));
}
}
return choices;
}
private static bool IsBoardCompletlyFilledIn(int[,] board)
{
for (int i = 0; i < board.GetLength(0); i++)
for (int j = 0; j < board.GetLength(1); j++)
if (board[i, j] == emptySpace) // if the space is equal to an empty space then the board is not filled in
return false;
return true;
}
// gets a list with all the possible moves
protected override List<Move> GetSolveList(int[,] boardToSolve)
{
List<Move> result = new List<Move>();
for (int i = 0; i < boardToSolve.GetLength(0); i++)
for (int j = 0; j < boardToSolve.GetLength(1); j++)
{
Move ?m = CheckMove(i, j, boardToSolve);
if (m != null)
result.Add((Move)m);
}
return result;
}
private Move? CheckMove(int x, int y, int[,] boardToSolve)
{
// empty check
if (boardToSolve[x, y] != emptySpace)
return null;
//Debug.WriteLine("wa");
// loop two times for checking 0 and 1
for (int i = 0; i <= 1; i++)
{ int opposite;
if (i == 0)
opposite = 1;
else
opposite = 0;
// check if it is a valid move
if (DoAllChecks(x, y, boardToSolve, opposite))
{
//Debug.WriteLine($"true {x} {y} {i}");
return new Move(x, y, i);
}
}
// if both 0 and 1 fail, then the move is invalid and null is returned
return null;
}
// shorthand for all the checks in one function
private static bool DoAllChecks(int x, int y, int[,] board, int checkFor)
{
return MiddleCheck(x, y, board, checkFor) ||
SideCheck(x, y, board, checkFor) ||
EvenCheck(x, y, board, checkFor);
}
// check if the space is surrounded on both sides by the same number. If it is, the checked space should be the opposite number
private static bool MiddleCheck(int x, int y, int[,] b, int checkFor)
{
// first check if x-1 and x+1 aren't out of bounds
// after that do the check if the move is valid
if(!(x-1 < 0 || x+1 > b.GetLength(0) - 1))
if (b[x - 1, y] == checkFor && b[x + 1, y] == checkFor)
return true;
// same for y
if (!(y - 1 < 0 || y + 1 > b.GetLength(1) - 1))
if (b[x, y - 1] == checkFor && b[x, y + 1] == checkFor)
return true;
// return false if nothing was found
return false;
}
// check if the two spaces left, right, up or down of the space are the opposite number. if so return true
private static bool SideCheck(int x, int y, int[,] b, int checkFor)
{
//check the two spaces left
if (x - 2 >= 0)
if (b[x - 2, y] == checkFor && b[x - 1, y] == checkFor)
return true;
//check the two spaces right
if (x + 2 < b.GetLength(0))
if (b[x + 2, y] == checkFor && b[x + 1, y] == checkFor)
return true;
//check the two spaces down
if (y - 2 >= 0)
if (b[x , y- 2] == checkFor && b[x , y- 1] == checkFor)
return true;
//check the two spaces up
if (y + 2 < b.GetLength(1))
if (b[x , y+ 2] == checkFor && b[x , y+ 1] == checkFor)
return true;
return false; }
// every row and colom should have an even number of 1'boardSize and 0'boardSize. So if the total number of 1'boardSize in a row is equal to half the with of the row a 0 should be filled in.
private static bool EvenCheck(int x, int y, int[,] b, int checkFor)
{
// check for a row and colum (provided that the width and height of the board is the same)
int countRow = 0, countCol = 0;
for (int i = 0; i < b.GetLength(0); i++)
{
if (b[i, y] == checkFor) countRow++;
if (b[x, i] == checkFor) countCol++;
}
// if there are more counted then possible return false
if ((countRow) > b.GetLength(0) / 2 || (countCol) > b.GetLength(0) / 2)
return false;
// check if the total number of oppisite numbers is equal to half te widht/heigt
if (countRow == b.GetLength(0) / 2 || countCol == b.GetLength(1) / 2)
return true;
return false;
}
public override void TileInput(Point? p, Keys k)
{
if (p == null) return;
int num = (int)k - 48;
if (num==0 || num==1 || num==2) boardState[((Point)p).X, ((Point)p).Y] = num%2;
}
public override void TileClick(Point p, int x)
{
if (boardState[p.X, p.Y] == emptySpace)
{
boardState[p.X, p.Y] = x;
return;
}
if (boardState[p.X, p.Y] == x)
{
boardState[p.X, p.Y] = 1 - boardState[p.X, p.Y];
return;
}
if (boardState[p.X, p.Y] == 1 - x)
{
boardState[p.X, p.Y] = emptySpace;
}
}
}
}