Logical point

 apk Download link ： Resource sharing summary

The rules of the game ： Put the dots in a square , Make the number of dots in each row and column the same as the given number , And the dots are divided into a group according to the adjacent , The grouping result should be the same as that given

implicit rules ： Each group is 1*n The shape of the , One group is completely separated from the other , That is, one group of dots is not the eight neighbors of another group of dots

In the appropriate place below , I explained in turn 5 A way ：

Method 1 ： Processing of minimal numbers

Method 2 ： The processing of maximal numbers

Method 3 ： Each group is mutually exclusive

Method four ： Optional group

Method five ： Enumeration of large group locations

（1）

   

Method 1 ： Processing of minimal numbers

Each grid ends up with only 2 States , With and without dots

When the number of dots whose positions have been determined in a row reaches the number calibrated in that row , Then no dots will be placed in other grids , The same goes for column .

Including special circumstances ： If the number is 0, This business （ Column ） Just mark it out without dots .

This seems useless , In fact, the key is that those who already know the final state must be marked out first , It will have an impact on the later work .

Method 2 ： The processing of maximal numbers ：

It is the same as the treatment of minimal numbers , When it is possible to put dots in a line （ Including determining the rounding point ） When the number of positions of is equal to the number marked on this line , These grids must be filled with dots , It should be marked immediately , The same goes for column .

Including special circumstances ： If the number is the length and width of the chessboard size, So this business （ Column ） Just put dots .

（2）

   

（3）

   

（4）

   

（5）

   

（6）

   

（7）

   

（8）

   

（9）

   

（10）

   

（11）

   

（12）

   

（1）

   

（2）

   

（3）

   

（4）

   

（5）

   

（6）

   

（7）

   

（8）

   

（9）

   

（10）

   

（11）

   

（12）

   

（13）

   

（14）

   

（15）

   

（16）

   

（17）

   

（18）

   

（19）

   

（20）

   

（21）

   

（22）

   

（23）

   

（24）

   

（25）

   

（26）

   

（27）

   

（28）

   

（29）

   

（30）

   

（1）

   

（2）

   

（3）

   

（4）

   

（5）

   

Method 3 ： Each group is mutually exclusive

Because the groups are mutually exclusive , So we can make sure that some grids have no dots

For the convenience of narration, it can be divided into 2 Species group ：

（1） A group of single dots , For example, this article （5） Guan will eventually have 2 Such a group

A group of single dots , Its eight neighbors do not put dots

（2）n(n>1) A group of dots , If the direction of this group is determined （ The positions of all dots in this group may not be determined yet , But it is certain that 2 The position of a dot determines whether the direction is horizontal or vertical ）, Then the eight neighbors of each dot are centered , Not in the row of this group 6 All the neighbors don't put dots

Here is the dot of the black triangle , Of its neighbors 6 One is the one without dots , For the nature beyond the boundary, it directly ignores

Next , Deal with it in terms of a maximum number ：

Last ：

（6）

   

（7）

   

（8）

   

（9）

   

（10）

   

（11）

   

（12）

   

（13）

   

（14）

   

（15）

   

（16）

   

（17）

   

（18）

   

（19）

   

（20）

   

（21）

   

Be careful , Although the final state of the lattice is only 2 Kind of , But if it is a prompt grid , Then besides giving the son itself , I also know about my neighbors .

In fact, that's right 《 Method 3 ： Each group is mutually exclusive 》 Development of .

That is to say, what can be determined at the beginning is ：

Method four ： Optional group

If a line （ Column ） Almost certain but not certain , Consider the limitations of optional groups

Like this one , Only 1*4 Group , No, 1*3 Group , So the first 4 Yes, it must be 1*4 Group

Continue to use 《 Method four ： Optional group 》, And to be with 《 Method 3 ： Each group is mutually exclusive 》 Combine

Now there is only 2 individual 1*2 Group and 2 individual 1*1 Group

If the first 6 Line is 1*2 Of the group, then 1、2 OK, let's put 3 A set of , It's obviously impossible ,

So the first 6 Yes, it must be 2 individual 1*1 Group , The first 1、2 Yes, it must be 2 individual 1*2 Group , And one horizontal and one vertical

So the answer comes out , Because of the existence of symmetry , The answer is not unique

（22）

   

（23）

   

（24）

   

（25）

   

（26）

   

（27）

   

（28）

   

（29）

   

（30）

First, use method one, two, three

Method five ： Enumeration of large group locations

Think about how to put the longest group , Enumerate all possible situations

Like this one ,1*3 The group must be standing upright , And in the 1 Column or column 3 Column or column 6 Column

If in the first place 1 Column or column 6 Column , According to method one, two and three, we can get , There is no solution

If in the first place 3 Column , According to method one, two and three, we can get the solution very quickly

thus ,4*4 Of ,5*5 Of ,6*6 All customs clearance .

There is a bigger chessboard in the back , But I have summarized the methods needed , It's just a lot of calculation .

If the amount of calculation is too large , It can also be programmed to solve , My code is in another blog post ： Battleship series