Greedy Queens Problem

In the famous Queens Problem, you need to put n chess queens on an n x n chessboard so no two queens attack each other. It has been proven that a solution exists for all n except n=2,3.

One of the methods (albeit an ineffective one) to solve it is by greedy algorithm, which does a depth-first search. In this case, a queen is placed on the first row, on the first column. The next queen is placed on the second row, starting from the first column. As it attacks a previous queen, it is moved to the second column, and again to the third column. Now as they don’t attack, a third queen is placed from the leftmost column rightward, and so on. When a queen cannot be placed, the previous queen is removed and placed to the next column. This guarantees a solution, as it checks every possible board as long as no conflict has been made.

For example, with n=4:
First queen tries a1.
Second queen tries a2. Conflict with a1.
Second queen tries b2. Conflict with a1.
Second queen tries c2.
Third queen tries a3,b3,c3,d3 in order but conflicts each time. Second queen is retracted.
Second queen tries d2.
Third queen tries a3, conflict with a1.
Third queen tries b3.
Fourth queen tries a4,b4,c4,d4, all conflict. Third queen is retracted.
Third queen tries c3,d3, all conflict. Third queen is retracted. Second queen is retracted (cannot go further).
First queen tries b1.

This algorithm is run until the solution b1,d2,a3,c4 is found (the first solution found). In total, there are 26 queen tries.

For n=5, it can be verified that it takes 15 queen tries to arrive at a1,c2,e3,b4,d5.

Can you compute the number of queen tries for a given n effectively? In other words, is this problem in P? (Naively executing the algorithm gives a possible n^n steps, so it’s not polynomial. You need a better way.)

Extra Problem

A revised version of the algorithm doesn’t put a queen when it makes a conflict. So, for the n=4 example above, we have:

First queen on a1.
Second queen can’t go on a2,b2. Second queen on c2.
Third queen can’t go anywhere, second queen is retracted and go on d2.
Third queen on b3.
Fourth queen can’t go anywhere. Third queen retracted. Second queen retracted. First queen on b1.
And so on.

It takes 8 queen tries now. For n=5, it takes 5 queen tries, or in other words the exact number required.

Can you compute this number effectively too?

Furry

Anyone reading all my previous blog entries (like, since second half of 2012) should have known that I’m pretty much a furry. As in I have a fondness of furry animals/anthros/whatever.

Yet Another Favorite List

1. Sky Shaymin
2. Glaceon
3. Sylveon
4. Dratini
5. Leafeon
6. Eevee
7. Dragonite
8. Fennekin
9. Keldeo
10. Uxie

Whee. Eeveelutions begin to rule my favorite list, although Skymin is far, far ahead the others.

Hidden Contest

Yes, yesterday was April Fools, and I tried to make it a “reverse hoax”. That “random puzzle” is not entirely random. If you haven’t found where you should put the answer key, then you’re just starting.

Also I found an ambiguity; I’ll fix it later.

On an unrelated note, I’m now on #PMD-Explorers group at deviantArt. Whee.

Puzzle 59: A Random Puzzle

Tapa Shade some cells black so the black cells form a single polyomino. A cell containing numbers may not be shaded black. Numbers in a cell indicate the length of connected black cells around the cell (cells that share a vertex with it). If there are at least two numbers, they must be separated by at least one white cell. A question mark stands for some non-zero number, and it might not be consistent across the puzzle.

Difficulty 2.0/10 Master time 2:00 Expert time 3:30

Puzzle 59: A Random Puzzle
Tapa

So I’m feeling really uninspired for today.

Oh wait, I missed something.

Answer key: Count the number of black cells.

…answer key? Wait, something is not right here.

EDIT: Puzzle edited. If you have just started though, it might not be of your concern.

ContractGrid

A weird trick-taking card game I thought, for three players. Inspired by those games with missions. I haven’t tested it though, and asking for anyone that wants to playtest it to test it.

Puzzle 58: That Classic Board Game

Mastermind There is a hidden 5-digit string, where its characters are among 1-9 only, but the characters may repeat. The objective is to discover this string. There are several guesses that has been made about the string. Each guess is a string of the same length and from the same character set, and its response is a number of black circles and/or white circles (might be none). A black circle indicates a character that exists in the hidden string and is on the correct position, while a white circle indicates a character that exists in the hidden string but is not on the correct position. For example, if the hidden string is 11223 and the guess is 13123, three black circles for the first 1, the 2, and the last 3, and a white circle for the other 1 will be awarded.

Difficulty 1.5/10 Master time 0:20 Expert time 0:50

Puzzle 58: That Classic Board Game
Mastermind

Whee. This thing is easy to make in head. This puzzle, not this genre. I’m sure it’s possible to make a difficult puzzle in this genre.

Also, note that Puzzle 57 has reached the fifth version, which I hope to be unique.

Finally, stay tuned. I’ll post one or two more puzzles soon.

Protected: Testing whether LMI can read this post or not. The password is “hi”.

This content is password protected. To view it please enter your password below:

Password:

Puzzle 57: Ridiculous Changes

Fillomino Operations Divide the grid into polyominoes. Fill each cell inside a polyomino by the size of the polyomino, after applying all mathematical operations it contains (multiplication/division before addition/subtraction). For example, a 5-square polyomino containing -3 and ×2 will have the number 5×2-3 = 7 on each of its cells. Polyominoes that contain the same number may not be orthogonally adjacent.

Difficulty 6.5/10 Master target 4:00 Expert target 12:00

Puzzle 57: Ridiculous Changes
Operation Fillomino

EDIT: VERSION 5 fajshnkkbkxmidcvger I hope it’s the last update. I’m pretty sure it has a unique solution, but my intended solution requires a really large-scale (as in the whole thing) deduction as the first step. And hence, the expert time is doubled. Whee.

Erm. So I lied and posted a new puzzle before April. This was made while I was doing chemistry finals (after completing it).

Yes, I believe that 6.5/10 is accurate for a 7×7 grid, but I didn’t give this to my testsolvers so I don’t know what the others think. I’m giving this now, and I’ll edit the difficulty/time later after getting responses.

If you find the rules hard to understand, I suppose I should post an example…

Also, did you notice Puzzle 28 and FFF 25 are redone? (The originals were broken and I gave up finding a way to fix them.)

FFF 25: Yet Another Explosion

Norinori Fillomino Follow regular Fillomino rules. In addition, the regions form a valid Norinori grid: It must be possible to shade exactly two squares in each polyomino such that each black square is adjacent to exactly one other black square.

Difficulty 3.0/10 Master target 1:30 Expert target 2:30

FFF 25: Yet Another Explosion
Norinori Fillomino

Another out-of-sequence puzzle. The original FFF 25.

Also, it’s great that the original puzzle was broken; I managed to fit a polyomino of size over 4 times the largest given in this puzzle. Yay.