Takuzu Solver

Statement

Goal

Your program must output a solution to a Takuzu.
A Takuzu, also known as Binairo, is a logic puzzle involving placement of two symbols (0 and 1) on a square grid.

The objective is to fill the grid with 1s and 0s, constraints are :
- an equal number of 1s and 0s in each row and column
- no more than two of either number adjacent to each other
- no identical rows and no identical columns

Similar to Sudoku, each puzzle begins with several squares in the grid already filled. Each test has only one possible solution.

Input

Line 1 : an integer n, dimension of the square grid.
n lines : a string line with n digits corresponding to that line. A "." is used for an empty space.

Output

n lines : A string line with n digits corresponding to that line. The original numbers should not have changed, and there should be no "." left.

Constraints

0 < n <= 20
n is an even number

Example

Input

4
.1.0
..0.
.0..
11.0

Output

Comments

16 Comments

StepBack13 Unnamed CodinGamer

about 9 months ago

Hey, I made an easy version of this puzzle without realising there was already a hard version (I was thinking of making a hard version later). Let me know what you think of the easy one and if you think it's worth having both? https://www.codingame.com/... I had "_" as the empty spaces originally, but changed to "."s now to match your inputs.

Alcalyn Unnamed CodinGamer

over 3 years ago

✅ Approved the contribution. Comment: Thanks fir this puzzle!

Razovsky Unnamed CodinGamer

✅ Approved the contribution. Comment: I would love to see this accepted, did a lot of them on paper, hope a last person will validate it !

tabasavr Unnamed CodinGamer

Your constraint is n <= 20, but you don't have any tests larger than 12

TheMagicShop Unnamed CodinGamer

For clarity, I would change "no identical rows or columns." by "no identical rows and no identical columns." since a row can be identical to a column (if you convert them in binary).

vinc-r Unnamed CodinGamer

Ok, it's done :)

Westicles Unnamed CodinGamer

✅ Approved the contribution. Comment: Fun puzzle. Probably should be medium.

Thank you ;) It was firstly medium, then I changed it to hard according to Konstant's comment. So I don't really know what to do...

Konstant Unnamed CodinGamer

I like this logic puzzle. Good job. i think the difficulty of puzzle is hard. It's similar difficulty to https://www.codingame.com/... and https://www.codingame.com/.... Even if you know what you need to check its still plenty of coding. In statement I would add, that each test has only one possible solution.

Hello Konstant, Thank you for your comment ;) I'm not sure that it's a hard puzzle, because there is a Sudoku solver and Futoshiki solver in medium puzzle. https://www.codingame.com/... https://www.codingame.com/... They are also logical puzzles in a square grid with a recursive solution. What do you think about it ? I added the only one solution in the statement.

Hello, If you have code improvement idea, don't hesitate to submit them to me so I can improve the solution. You're welcome to do any other suggestion, I would be glad to improve the puzzle.

Cool one! I read too fast the statement, I think constraints should be displayed as list instead of paragraph, something like: The objective is to fill the grid with 1s and 0s, constraints are: - an equal number of 1s and 0s in each row and column - no more than two of either number adjacent to each other - no identical rows or columns.