using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Linq;
using System.Runtime.CompilerServices;
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 = 8) // should be even
{
boardState = GetClearBoard(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\r\n- Each row and column cannot appear multiple times on the board";
}
public override void Draw (Graphics gr, Point p, Size s)
{
gr.FillRectangle(Brushes.Beige, p.X, p.Y, s.Width, s.Height);
for (int i = 0; i < boardState.GetLength(0); i++)
{
for(int j = 0; j < boardState.GetLength(1); j++)
{
gr.DrawRectangle(Pens.Black,
p.X+i*s.Width/ boardState.GetLength(0),
p.Y+j*s.Height/boardState.GetLength(1),
s.Width / boardState.GetLength(0),
s.Height / boardState.GetLength(1));
if (boardState[i,j] == 0)
{
gr.FillEllipse(Brushes.White,
(int)(p.X + ((double)i + 0.125) * s.Width / boardState.GetLength(0)),
(int)(p.Y + ((double)j + 0.125) * s.Height / boardState.GetLength(1)),
s.Width / boardState.GetLength(0) * 3 / 4,
s.Height / boardState.GetLength(1) * 3 / 4);
}
if (boardState[i, j] == 1)
{
gr.FillEllipse(Brushes.Black,
(int)(p.X + ((double)i + 0.125) * s.Width / boardState.GetLength(0)),
(int)(p.Y + ((double)j + 0.125) * s.Height / boardState.GetLength(1)),
s.Width / boardState.GetLength(0) * 3 / 4,
s.Height / boardState.GetLength(1) * 3 / 4);
}
}
}
}
// static meathode for filling a int[,] with -1
public static int[,] GetClearBoard(int boardSize)
{
int[,] result = new int[boardSize, boardSize];
// fill the board with empty spaces (-1)
for (int i = 0; i < boardSize; i++)
{
for (int j = 0; j < boardSize; j++)
result[i, j] = emptySpace;
}
return result;
}
// generates a random solvable board
public override void Generate()
{
// start with a clear board
int[,] startBoard = GetClearBoard(boardState.GetLength(0));
// generate a board
int[,] generatedBoard = BackTrackAlgorithm(startBoard);
boardState = generatedBoard;
}
private static int recursionDepth = 0;
private static int maxDepth = 1000000; // 1 mil recursions are allowed
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));
}
// 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
private static int[,] BackTrackAlgorithm(int[,] board)
{
recursionDepth++;
if (recursionDepth > maxDepth)
{
Debug.WriteLine("Max recursion depth reached.");
return board;
}
// print board for debugging
//PrintBoard(board);
// check if the board is complete. if so then we can return the result
if (IsBoardCompletlyFilledIn(board))
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)
{
//Debug.WriteLine("backtrack want count ==0");
return null; // backtrack
}
// check if the current board is already imposible to complete even tho there are still choices left
if (!BoardIsPosible(board, choices))
return null;
///*
// shuffle the choices in the list around to get different results every time
// First answer from: https://stackoverflow.com/questions/273313/randomize-a-listt
Random random = new Random();
int n = choices.Count;
while (n > 1)
{
n--;
int rand = random.Next(n + 1);
Move copy = choices[rand];
choices[rand] = choices[n];
choices[n] = copy;
}
//*/
// 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;
int[,] result = BackTrackAlgorithm(newBoard); // recursion for every move
if(result != null)
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;
}
}
}