C#: Using Permutations to solve Shikaku game through brute-force
Introduction
In this article we will see how it is possible to solve a Shikaku – a Japanese logic game - through a C # program, exploiting the computational power of our machines to calculate all the possible potentially valid combinations in the played game, to find among them the one valid only. Although the brute-force approach (ie the progressive calculation of all the possible combinations of a given problem, until the valid solution is reached) is disadvantageous for processing with a high number of possibilities, in this case, it will be used to consider the more generic problem, and also because the focus of the article does not want to be the optimal solution, but rather the analysis of the process that gives a partially graphical problem allows us to deduce a possible code approach. Before moving on to the practical part, we therefore see in detail what the Shikaku is, and then propose an idea of implementation and then implement it.
Prerequisites
- Microsoft Visual Studio
- Basic knowledge of C# language
Shikaku, introduction, and rules
Shikaku (shikaku ni kire, divide by squares) is a Japanese logic game published by Nikoli Co. Ltd, a publisher specializing in games, especially logical puzzles. Of the same publisher, it is - to give an example - even the most famous Sudoku. The Shikaku (literally, in Japanese, square) is played on a grid of equal rows and columns, which can extend from the dimensions of 5 x 5 up to 25 x 25 and above.
Some of the cells that make up the game grid are numbered. The goal of the game is to divide the grid into rectangles and squares such that each of these divisions contains only one of the numbers present, and that the area of that portion is equal to the number itself. This means that two grid divisions cannot overlap, that is, to share cells.
We report here to follow an example of Shikaku 11 x 11, with its solution:
Smaller grids are obviously simpler to solve, and yet we can be misled in selecting wrong areas and having to retrace our steps when we realize - continuing in the game - that we have chosen a division that leaves cells uncovered, or that puts in the condition of not having space necessary for adjacent solutions. Despite this, man has the advantage of being able to see the problem, and therefore to have at least an idea of the proportions that each rectangle or square must have. Not being able to replicate this feeling at the machine level, we will necessarily have to find another way to proceed.
Of course, we can start by conceiving the grid that makes up the entire Shikaku as a two-dimensional array (for example, bytes), with some elements of the whole that will be initialized to values conforming to a valid Shikaku. Assuming we want to represent a 5 x 5 grid, we can therefore, have a structure of this type:
private const int _SIZE = 5;
public byte[,] Cells { get; set; } = new byte[_SIZE, _SIZE];
Proposal for a solution to the problem
Each cell containing a value can be understood as a separate problem. Initially, in fact, we will have to worry about finding all the potential solutions of every single valued cell, that is the areas that can be occupied for each value, without worrying about the other cells. Secondly, we will compare the results obtained for a cell with those of each other cell, in order to analyze the collisions between areas. We will understand that this last part is undoubtedly computationally demanding: however, while we collect the various potential solutions for each cell, we can not discard any of them, because as long as we do not have all the possible configurations for each cell we will not be able to determine the complexity of collisions. In other words, discarding a configuration before getting it all and comparing it would result in the possible deletion of an element of the only valid solution.
Let's move on to a practical example that represents what we have just seen, and depict here to follow the procedure to be used to find possible solutions to three of the cells of a shikaku 5 x 5. In the case of images, cells [0,0], [ 4.0], [1,2]. As we will notice, we proceed to list the possible "movements" on the grid, or - starting from the position of the cell in question - which are the directions to be enlarged, until the desired area is obtained. In this phase, as anticipated, we will not worry about the overlapping solutions, but it goes without saying that in the second measure, for example, the solution 2 of the cell [4,0] will be discarded, because it would include the valued cell [4,3].
This is done for all the cells, and when the process is finished (that is, when all the solutions are available for each cell), we start to compare the combinations, as if they overlapped the slides. If the N superimposed slides (where N is the number of cells originally evaluated) do not have collisions, the correct solution has been found; vice versa, it will be necessary to continue the analysis of the remaining configurations.
Basic implementation
Moving on to the practical implementation, we try to realize what we have seen so far: we talked about a two-dimensional array to represent the grid, the need to calculate the extension of the value cells areas, and the need to recover all possible solutions for a given cell. Let's see a method to create all this using C#.
public class Area
{
public int Base { get; set; }
public int Height { get; set; }
}
public class CellSolutions
{
public List<Shikaku> PotentialSolutions { get; set; }
}
public class Shikaku
{
private const int _SIZE = 5;
public byte[,] Cells { get; set; } = new byte[_SIZE, _SIZE];
public List<CellSolutions> Solutions { get; set; } = new List<CellSolutions>();
private List<Area> FindAreas(int area)
{
var tmp = new List<Area>();
for(var row = 0; row < _SIZE; row++)
{
for (var col = 0; col < _SIZE; col++)
{
if (row * col == area) tmp.Add(new Area() { Base = row, Height = col});
}
}
return tmp;
}
public Shikaku() { }
}
The above is the minimum implementation to get the result premised. We have three classes, Area, CellSolutions, Shikaku. The latter will be the heart of our elaboration. As we will notice, it has the two-dimensional array of Cells cells, a List <CellSolutions> (which contains a List <Shikaku>, and it will be useful to store possible solutions), and finally the FindAreas function.
Note its operation: it requires an argument that represents the value of an area (that is, the number represented inside our cell), and on the basis of this - scrolling through the grid cells - it calculates all the possible base combinations for height that result in the cell's actual value. A List <Area> is then returned, which will be used in the calculation of possible solutions.
The latter can be implemented as follows:
private bool CompileArea(int row, int col, Area area, int rowToSolve, int colToSolve, int value)
{
var isCellInSolution = false;
int numOccupied = 0;
for(var r = row; r < row + area.Base; r++)
{
for(var c = col; c < col + area.Height; c++)
{
if (r < _SIZE && c < _SIZE)
{
++numOccupied;
this.Cells[r, c] = 99;
if (r == rowToSolve && c == colToSolve) isCellInSolution = true;
}
}
}
if (numOccupied != value) isCellInSolution = false;
return isCellInSolution;
}
In other words, we implement a method that receives as a parameter the row/column position (cell) to be solved, an Area object, and the area value present in the cell. Then scroll the rows and columns up to the maximum extent of area.Base and area.Height, and within that cycle verify at the same time that it is still within the grid. This last check is useful to avoid that areas that exceed the grid (that is, that we have a number of available cells smaller than those needed) are considered correct. Finally, the value of 99 is imposed on the considered cell (assuming to deal with Shikaku small enough to never expose 99 as the initial cell value). If this cell has the same coordinates as the one to be resolved, we return a Boolean indicating that the area involves our cell, so it is a candidate to be a potential solution. A final check verifies that the selected cells match with the cell value: if not, the area must not be considered valid.
We will use this method in the context of a further function, appointed to find all the possible solutions of a single cell
public List<Shikaku> SolveSingleCell(int row, int col)
{
var shikakus = new List<Shikaku>();
int value = this.Cells[row, col];
var areas = FindAreas(value);
for(var r = 0; r < _SIZE; r++)
{
for(var c = 0; c <_SIZE; c++)
{
foreach (var a in areas)
{
var shikaku = new Shikaku();
if (shikaku.CompileArea(r, c, a, row, col, value))
{
shikakus.Add(shikaku);
}
}
}
}
return shikakus;
}
The SolveSingleCell method accepts the coordinates of a cell to be solved as arguments. It then prepares a list of Shikaku objects, scrolling through the grid the areas calculated for the cell value, and verifying that they fall into the selected cell, in which case we will consider the shikaku calculated as valid, that is as a potentially overlapping potential solution.
Hypothesizing then the case of a cell to be solved, we then graphically see what would be the result of the SolveSingleCell method, or what are the shikaku produced and returned (which, as we will recall, will be considered as "slides" to compare with those of the other cells)
We can then think of storing these three possible solutions in the List <CellSolutions> of the Shikaku of origin, in order to be able to return to it later. It goes without saying that to find all the possible solutions of all the cells it is sufficient to iterate the above method for each cell of the original Shikaku, memorizing the results returned for each cell.
public void GetAllSolutions()
{
for (var r = 0; r < _SIZE; r++)
{
for (var c = 0; c < _SIZE; c++)
{
if (this.Cells[r, c] > 0)
{
this.Solutions.Add(new CellSolutions() { PotentialSolutions = SolveSingleCell(r, c) });
}
}
}
}
We can see in the GetAllSolutions method how, for each cell that has a value greater than zero, the SolveSingleCell method is executed to compile a potential list of solutions. At the end of this cycle we will have in the Solutions property as many objects as will be the cells of the original Shikaku, and for each of them, the PotentialSolutions property will contain all possible cell solutions. There will, therefore be only to compare them to find the only solution to the initial problem.
Permutations check
We introduce a trivial but important method: how can we know if two Shikaku collide with each other? In other words, we must be able to know if two possible candidates try to occupy one or more common cells.
private bool IsColliding(Shikaku s1, Shikaku s2)
{
for(var r = 0; r <_SIZE; r++)
{
for(var c = 0; c < _SIZE; c++)
{
if (s1.Cells[r, c] == s2.Cells[r, c] && s1.Cells[r,c] == 99) return true;
}
}
return false;
}
Given two Shikaku objects of the same size, it will be sufficient to analyze each of their cells, verifying that at the same row and column both contain the value of 99. In that case, the two collide. If the test is passed, the two squares are potentially compatible because they are not overlapped at any point.
Thanks to this method, we can now think of a function that controls the permutations of each potential solution. We will solve this problem by thinking of it as a padlock with a numerical combination. In fact, it has just been said that the Solutions property has a length equal to that of the cells evaluated and that each Solutions [x] contains all the possible combinations that solve this cell (PotentialSolutions).
Let's assume we have a Shikaku with 5 valued cells. For each of these, 4, 2, 3, 6, 2 potential solutions were calculated respectively. The Solutions property, having a variable number of PotentialSolutions for each object, can then be represented as follows:
Consequently, we can use a one-dimensional array (in the case of the example, of length 5), which we will scroll as if it were a combination lock, where the possibility of scrolling a certain position is given by the number of potential solutions for that position. Whenever the Potential Solutions are exhausted in a Solutions, it will return to it starting from the zero index. For each tested configuration, the collisions between each Shikaku that composes the solution will be checked, and if these occur, proceed until the correct one is found.
We can therefore, write a method that achieves the above:
private List<Shikaku> CheckPermutations(List<CellSolutions> shikakus)
{
int rank = shikakus.Count;
if (rank <= 0) return null;
int[] indexes = new int[rank];
int parser = 0;
Shikaku[] solution = new Shikaku[rank];
bool isValid = false;
while (!isValid)
{
solution = new Shikaku[rank];
// Riempio list con la combinazione corrente di shikaku potenziali
for (int i = 0; i < rank; i++)
{
if (indexes[i] > shikakus[i].PotentialSolutions.Count - 1) {
indexes[i] = 0;
++parser;
if (parser >= rank) parser = 0;
}
solution[i] = shikakus[i].PotentialSolutions[indexes[i]];
}
// Verifico se gli elementi inseriti nella soluzione potenziale collidono tra loro
bool collides = true;
for (int i = 0; i < solution.Length; i++)
{
for (int j = 0; j < solution.Length; j++)
{
if (i == j) continue;
collides = IsColliding(solution[i], solution[j]);
if (collides) break;
}
if (collides) break;
}
isValid = !collides;
++indexes[parser++];
if (parser >= rank) parser = 0;
}
return solution.ToList();
}
As we will notice, the code is rather simple. The part to pay more attention to is obviously the part that manages our "padlock", here represented by the one-dimensional indexes array. It will gradually contain all the permutations of indices to be tested, which will be done using the IsColliding method previously seen. It goes without saying that the greater the boxes and the size of the shikaku, the greater the resolutive complexity and the possibilities at stake (therefore, the time necessary to extract the correct solution). Like the methods highlighted above, CheckPermutations also returns a List <Shikaku> object. The latter will contain the individual "slides" for each cell that will result non-overlapping. In other words, each index will correspond to its only potential solution that does not collide with any other element in the list.
Shikaku solution
At this point, the resolution of the shikaku consists of the simple combined use of the methods seen so far.
public void SolveShikaku()
{
this.GetAllSolutions();
var valid = CheckPermutations(this.Solutions);
foreach(var v in valid)
{
v.ConsolePrint();
}
}
The SolveShikaku function will first deal with finding solutions for each cell through GetAllSolutions, then run the CheckPermutations method on them and return the List <Shikaku> containing the solution. By cycling on each element of it, we can produce - for example on screen - the list of shikaku representing the rectangles for each value cell.
The ConsolePrint method, written just for this purpose, does nothing but emit the contents of a Shikaku in the form of a grid.
public void ConsolePrint()
{
Console.WriteLine("=====================================================================================");
for(var row =0; row < _SIZE; row++)
{
for(var col = 0; col < _SIZE; col++)
{
Console.Write("{0} ", this.Cells[row, col].ToString("00"));
}
Console.WriteLine();
}
Console.WriteLine("=====================================================================================");
}
Use and test
Once the class has been implemented, its use is simple. For example, consider the following snippet:
static Shikaku quadrato = new Shikaku();
quadrato.Cells[0, 2] = 3;
quadrato.Cells[1, 2] = 3;
quadrato.Cells[1, 3] = 2;
quadrato.Cells[1, 4] = 2;
quadrato.Cells[2, 0] = 3;
quadrato.Cells[2, 4] = 2;
quadrato.Cells[3, 0] = 4;
quadrato.Cells[3, 3] = 4;
quadrato.Cells[3, 4] = 2;
quadrato.ConsolePrint();
Console.WriteLine("********************************************************************");
quadrato.SolveShikaku();
Console.Read();
One proceeds to define an object of the Shikaku type, then taking care to value the initial cells with congruent values (obviously, these values must contribute to a resolvable grid). By running the ConsolePrint method on the object so valued, we will be able to see the original square. Recalling the SolveShikaku method will then start the search for the only valid solution, and when it is found, the rectangles corresponding to each cell will be displayed in the console.
In the above example, the solution is found in about 3 seconds on the test machine, producing an output like the one in the figure.
The additionally calculated rectangles are visible by scrolling the terminal screen resulting from the execution of the example.
Source Code
The source used in this article can be freely downloaded at https://code.msdn.microsoft.com/C-Permutazioni-nella-41f2592f
Other languages
The present article is available in the following localizations: