A simple algorithm for checking victory in a cross on a non-standard field

Faced such a problem that for young programmers who are just starting to learn languages, algorithms cause more difficulties than the syntax of the language. If the syntax and concept is explained by the teacher in a specific language, then you will have to invent the algorithms yourself. The exception to the rules can only be specialized technical specialties in universities, where they teach algorithms.

Given that the solution algorithm can be very simple, many do not know how to approach the solution of the problem. I will consider an example of checking victory in a tic-tac-toe game, but on a 6x6 field and a block of consecutive filled values ​​equal to 4th.

Actually, here is the universal algorithm, only instead of variables I used constants. And it practically does not depend on the language in which this check is carried out. I suggest that novice programmers first solve the problem graphically, and then translate it into one or another language. To create this algorithm, a sheet in a cage and a pen is suitable.
')
So, we have a 6x6 field.



A block of consecutively filled elements, which is enough to win, equals 4th.



I think that now (just a field of two figures) it has become much clearer how to solve this problem.

In fact, we have to solve 2 independent tasks:

1. Find all completed sequences in a 4x4 block.
2. Find all 4x4 squares in a 6x6 square.

1. Find all completed sequences in a 4x4 block

Why check block 4x4? Everything is simple in it, only 2 diagonals of this dimension are possible, which we need.

Using binary logic (1 & 1 = 1 and 1 & 0 = 0) we can easily make a check in cycles. To do this, we need 1 variable for each diagonal. Let toright be a logical variable in which we write the result of the diagonal from top left to right. And toleft to check the diagonal from top right down to left.

Initially, we set the value to true for these variables. Then we compare each cell in the diagonal with the symbol "X" or "O". Of course, we do it with 2 calls or compare everything with “X” or all with “O”.

We compare each cell of the diagonal with our symbol and get the result (true) or (false). Then, doing a logical operation (&) between the result and our toright. We write the result of this operation again to toright. If at some stage we get the result (false), then all further toright will always be equal (false). This follows from the rule of logical operations (1 & 0 = 0).

Let's write this on Jave:

boolean checkDiagonal(char symb) { boolean toright = true; //    1 for (int i=0; i<4; i++) { //   0  3 toright = toright & (map[i][i] == symb); } //    (true),        symb if (toright) return true; //   (false),     ,   symb return false; } 

Actually here in this line

 toright = toright & (map[i][i] == symb)) 

and there is all the logic.

A brief entry looks like this:

 toright &= (map[i][i] == symb)) 

Only 2 results of work conditions are obtained:

 toright = toright & 0  toright = toright & 1 

For 2 diagonals, the full function code will look like this:

 /**   */ boolean checkDiagonal(char symb) { boolean toright, toleft; toright = true; toleft = true; for (int i=0; i<4; i++) { toright &= (map[i][i] == symb); toleft &= (map[4-i-1][i] == symb); } if (toright || toleft) return true; return false; } 

Full analogue is done to check the verticals and contour lines, only the cycles change.

 /**      */ boolean checkLanes(char symb) { boolean cols, rows; for (int col=0; col<4; col++) { cols = true; rows = true; for (int row=0; row<4; row++) { cols &= (map[col][row] == symb); rows &= (map[row][col] == symb); } //         //    ,   //     . if (cols || rows) return true; } return false; } 

Actually this is the solution for the 4x4 block. As can be seen from the code, for another block you only need to change 4 in the loop for another number, or write the name of the variable instead of number. Moreover, you can make this variable as a global visibility, and pass to a function, for example:

 boolean checkLanes(char symb, int block)….. 

2. Find all 4x4 squares in a 6x6 square

Actually, they are not so many. Starting from the position [0,0], [1,0] and [2,0] for the first row of the square, [0,1], [1,1] and [2,1] for the second, [0,2] , [1,2] and [2,2] for the third. Further, the 4x4 square will go beyond the 6x6 square.

We can do this sorting of coordinates in cycles:

 boolean checkWin(char symb) { for (int col=0; col<3; col++) { for (int row=0; row<3; row++) { //         , //  ,    ,  //      if (checkDiagonal(symb, col, row) || checkLanes(symb, col, row)) return true; } } //     . 4-  //   .    . return false; } 

Here we will have to slightly modify the checkDiagonal and checkLanes methods, since we have to check the 4x4 square with the corresponding offset.

 int size = 6; //    int block = 4; //   boolean checkLanes(char symb, int offsetX, int offsetY) { boolean cols, rows; for (int col=offsetX; col<block+offsetX; col++) { cols = true; rows = true; for (int row=offsetY; row<block+offsetY; row++) { cols &= (map[col][row] == symb); rows &= (map[row][col] == symb); } if (cols || rows) return true; } return false; } 

I would recommend novice programmers to modify the checkDiagonal code themselves, since This will allow to better understand the principle of operation

And one more tip. At the moment there is a huge number of implementations of various algorithms in the network in different languages. If you want to learn to think, then look exactly the principles of solutions (algorithms) that are not tied to languages. Ready-made solutions will not allow you to quickly learn how to choose the most optimal solution. Very often, you can rewrite a ready-made solution from one language to another without understanding the principle of solving the problem. Somewhere this will help you, but somewhere it may make further development of the program impossible without changing its logic.

First, I recommend trying to write a check yourself. The game template can be picked up here . There are already header functions that I described in the article. It remains to copy part of my code into the template and modify it slightly. And here you can download the full working code in Java. I recommend to watch it after you have written your functions based on this article.