How to Solve Star-Placement Puzzles: Stars That Never Touch

To solve a star-placement puzzle, put the stated number of stars in every row, every column and every outlined region, and never let two stars touch, not even at a corner. You get there by ruling cells out: each star you place empties its whole row, its column, its region and the ring of cells around it, and those empty cells soon leave one place open somewhere else.

This guide explains the rules, the core moves, a full worked puzzle and a practice puzzle with its answer.

What is a star-placement puzzle?

A star-placement puzzle is a square grid divided into outlined regions of different shapes. The simplest version asks for one star in each row, one in each column and one in each region. Some grids ask for two stars in each.

There is one more rule, and it is the one that makes the puzzle work. No two stars may sit in neighbouring cells. That covers side by side, above and below, and diagonal corners too.

A good puzzle has exactly one answer, and you can reach it by reasoning alone, one forced step after another.

Why does the no-touching rule matter so much?

Picture each star as a chess king. A king can step to any of the cells around it, so a set of stars that never touch is a set of kings that can never reach each other in one step.

Chess-board mathematics has a neat tool for this kind of rule. A paper published on 8 December 2016 divided a board into small blocks of two rows by two columns and pointed out that two queens inside the same block are always on neighbouring squares ^[1]. Because of this, each block can hold at most one queen, so even with extra pieces placed to block their lines, queens can fill at most about a quarter of the board ^[1].

The same block trick works for stars. Any two cells of a two by two block touch, so a block can never hold more than one star. This simple fact settles many positions in larger puzzles, as you will see below.

How is it related to the dragon king problem?

A dragon king is a board-game piece that moves any distance along its row or column, or a single step diagonally ^[2]. A paper published on 31 December 2018 studied placements of these pieces, with a few blocking pieces added, in which no piece can reach another ^[2]. It noted that a row with no blocking pieces in it can hold at most one dragon king ^[2].

Without blocking pieces, the dragon king puzzle becomes very close to a one-star grid. Each row and column gets one piece, and no two pieces may be diagonal neighbours. The only thing missing is the regions. The paper also notes that this case was originally called the n kings problem ^[2].

What marks should you use?

You need two marks, and a pencil.

• A star for a cell that must hold a star.
• A dot for a cell that cannot hold one.

Put a dot only when you can say why the cell is empty. When you place a star, add the dots at once: the rest of its row, the rest of its column, the rest of its region and all eight cells around it. Those dots are what lead you to the next star.

What are the core moves?

Five moves will carry you through a one-star puzzle. The table sets them side by side.

The squeezed region and the region bundle are really the same idea at different sizes. If two regions live entirely inside two columns, those columns must give their stars to those two regions. Nothing else in those columns can hold a star.

The shared neighbour move is easy to overlook. Suppose a region has only two open cells left, side by side. Whichever one gets the star, the cells directly above both of them will touch it. So those cells are empty, even before you know where the star goes.

What is the step-by-step method?

1. Find the tiny regions. A one-cell region is a free star. A two-cell or three-cell region is a strong lead.
2. Look for squeezed regions. Any region that fits in a single row or column empties the rest of that line.
3. Look for bundles. Count regions that live inside the same few rows or columns.
4. Check shared neighbours. For each small region, ask which outside cells touch all of its open cells.
5. Place, then ring. Each new star gets its dots straight away.
6. Scan for last cells. After every new dot, look along rows, columns and regions for a single open cell.
7. Check at the end. Every row, column and region should hold the right number of stars, with no pair touching.

How does the method solve a five by five puzzle?

Here is an original puzzle. Each letter marks the region a cell belongs to. Place one star in each row, each column and each region, with no two stars touching.

Try it first, then read on.

Step 1: the one-cell region. Region C is the single cell at row 3, column 3, so it holds a star. Dot the rest of row 3, the rest of column 3 and the ring of cells around it.

Step 2: region E moves down. Region E has three cells: row 4 column 4, row 5 column 4 and row 5 column 5. The first touches the star at row 3, column 3, so it is dotted. Both open cells of E are now in row 5, so E is a squeezed region and row 5 belongs to it.

Step 3: region D is forced. Region D can no longer use row 5, so its star is in row 4. In row 4, column 2 touches the first star and column 3 is already used. Only row 4, column 1 is left, so it gets a star.

Step 4: region A has one cell left. Columns 1 and 3 are used, row 3 is used, and row 2, column 2 touches the first star. Every other cell of region A is dotted except row 1, column 2. That cell gets a star.

Step 5: finish B and E. Row 1 now has its star, so region B can only use row 2, column 5. Column 5 is then used, so region E takes row 5, column 4.

In the finished grid below, the letter S marks a star and a dot marks an empty cell.

Check. Each row and each column has one star. The stars sit in regions A, B, C, D and E, one each. No two stars touch, not even at a corner. For this guide, we checked by computer every possible layout, and this is the only answer.

How many layouts would you face without regions?

Regions are what make the answer unique. Take them away, keep one star per row and column and keep the no-touching rule, and you get the dragon king count with no blocking pieces. The paper of 31 December 2018 lists these counts for small boards ^[2].

Grids smaller than the ones in the table have no valid layout at all, which you can check by hand. The counts grow fast, and a puzzle designer has to draw region borders that cut every one of those layouts down to a single survivor.

That also tells you something as a solver. Every region border is doing work. If a region looks oddly shaped, ask which layout it is there to block.

How does the two-star version change things?

In two-star grids, every row, column and region needs two stars, and the no-touching rule still applies. Single-cell moves are rarer, so counting moves take over.

The most useful one comes from the block idea above. Here is our own worked example, not taken from the paper. Take two neighbouring rows of a ten by ten grid. Together they need four stars, and they split into five two by two blocks. Each block holds at most one star, so four of the five blocks hold exactly one star and only one block is empty.

Once you mark a block as empty, every other block in that pair of rows must hold a star. Combine that with the regions, and stars start to drop into place.

Two habits help in two-star grids:

• When a region needs two stars and has only three cells in a line, the middle cell can never hold a star, because either neighbour would touch it.
• When two stars are already in a row, dot the rest of that row at once.

What are the most common mistakes?

• Forgetting the corners. Diagonal neighbours count as touching, and this is an easy rule to break.
• Ringing the star but not the region. A star also empties every other cell of its region.
• Stopping too early. If you feel stuck, look for a shared neighbour or a region bundle; a good puzzle always has a next step.
• Skipping the final check. Count stars in every row, column and region at the end.

Can you solve this practice puzzle?

Place one star in each row, each column and each region, with no two stars touching.

A hint if you need one: regions A and C sit side by side in the top right corner.

Answer: the stars are at row 1 column 6, row 2 column 3, row 3 column 5, row 4 column 2, row 5 column 4 and row 6 column 1.

Region A lies entirely in column 6, so region C cannot use column 6 and must take row 3, column 5. That star touches row 2, column 6, so region A takes row 1, column 6. Region B is now left with only row 2, column 3.

Region D can then only use row 4 or row 5 in column 2. If it took row 5, every open cell of region F would touch it or share its row, so D takes row 4, column 2, region F takes row 6, column 1, and region E takes row 5, column 4.

If you enjoy placing things on a grid under strict rules, try this live riddle next. It shows nine glass lanterns and asks which single tap lights all nine tiles.