Solve Hitori Puzzles

Question

Introduction

Write a solver for the Hitori puzzles using least bytes.

Challenge

Your task is write a solver for the Hitori (ひとり, the word for "alone" in Japanese; the meaning of the game name is "Leave me alone") logical puzzles. The rules are as follows:

• You are presented with a n-by-n grid of cells, each cell contains an integer between 1 and n (inclusive).
• Your goal is to make sure that no number appear more than once in each row and each column of the grid, by removing numbers from the given grid, subject to the restriction indicated in the next two rules,
• You cannot remove two numbers from two adjacent (horizontally or vertically) cells.
• The remaining numbered cells must be all connected to each other. It means that any two remaining numbered cells can be connected with a curve that is composed solely of segments connecting adjacent remaining numbers (horizonally or vertically). (Thanks to @user202729 for pointing out that this is missing)

I hope the rules are clear by now. If there is anything unclear about the rules, check the Wikipedia page.

Test Cases

The cells from which the numbers are removed are represented with 0s.

Input  ->  Output

4
2 2 2 4      0 2 0 4
1 4 2 3  ->  1 4 2 3
2 3 2 1      2 3 0 1
3 4 1 2      3 0 1 2

4
4 2 4 3      0 2 4 3
4 1 1 2  ->  4 1 0 2
3 1 2 1      3 0 2 1
4 3 1 3      0 3 1 0

5
1 5 3 1 2      1 5 3 0 2
5 4 1 3 4      5 0 1 3 4
3 4 3 1 5  ->  3 4 0 1 5
4 4 2 3 3      4 0 2 0 3
2 1 5 4 4      2 1 5 4 0

8
4 8 1 6 3 2 5 7      0 8 0 6 3 2 0 7
3 6 7 2 1 6 5 4      3 6 7 2 1 0 5 4
2 3 4 8 2 8 6 1      0 3 4 0 2 8 6 1
4 1 6 5 7 7 3 5  ->  4 1 0 5 7 0 3 0
7 2 3 1 8 5 1 2      7 0 3 0 8 5 1 2
3 5 6 7 3 1 8 4      0 5 6 7 0 1 8 0
6 4 2 3 5 4 7 8      6 0 2 3 5 4 7 8
8 7 1 4 2 3 5 6      8 7 1 4 0 3 0 6

9
8 6 5 6 8 1 2 2 9      8 0 5 6 0 1 2 0 9
5 6 2 4 1 7 9 8 3      5 6 2 4 1 7 9 8 3
5 8 2 5 9 9 8 2 6      0 8 0 5 0 9 0 2 0
9 5 6 6 4 3 8 4 1      9 5 6 0 4 3 8 0 1
1 1 6 3 9 9 5 6 2  ->  0 1 0 3 9 0 5 6 2
1 1 4 7 3 8 3 8 6      1 0 4 7 0 8 3 0 6
3 7 4 1 2 6 4 5 5      3 7 0 1 2 6 4 5 0
3 3 1 9 8 7 7 4 5      0 3 1 9 8 0 7 4 5
2 9 7 5 3 5 9 1 3      2 9 7 0 3 5 0 1 0 

These test cases are taken from Concept Is Puzzles, PuzzleBooks, Concept Is Puzzles, Wikipedia, and Youtube, respectively.

Specs

• No need to worry about exception handling.

• You can assume that the input is always a valid puzzle with a unique solution and you can take advantage of this in writing your code.

• This is code-golf, the lowest number of bytes wins.

• 4 <= n <= 9 (16 originally, changed to 9 following Stewie Griffin's suggestion, also save some trouble in IO)

• You can take input and provide output through any standard form, and you are free to choose the format.

• Some suggestions for the output format are (but you are not restricted to these)

  • Outputting the final grid
  • Outputting the grid containing all removed numbers
  • Output a list of coordinates of one of the above

• As usual, default loopholes apply here.

---

_{Related(inspired by this challenge): Check if All Elements In a Matrix Are Connected}

_{My last challenge: Extension of the Game of Sevens}

Answer 1

Haskell, 374 bytes

import Data.Array;import Data.List;r=range;p=partition
c(e,f)=p(\(b,p)->any(==1)[(b-d)^2+(p-q)^2|(d,q)<-e])f
n#g=[s|(o,(e:f))<-[p((==0).(g!))$indices g],
 null.fst$c(o,o),null.snd$until(null.fst)c([e],f),
 s<-case[((l,c),d)|((l,c),h)<-assocs g,h>0,
 d<-[filter((==h).(g!))$r((l,c+1),(l,n))++r((l+1,c),(n,c))],d/=[]]
 of[]->[g];((c,d):_)->n#(g//[(c,0)])++n#(g//[(c,0)|c<-d])]

Try it online!

Answer 2

Jelly, 62 bytes

Uses user202729's isConnected monadic link from another question.

---

FJṁa@µ«Ḋoµ€ZUµ4¡ÐLFQL<3
ḟ0ĠḊ€
¬T€œ&2\;Ç€FȦ
ZÇȯÇ_1Ŀ
2ḶṗLṗLa⁸ÇÞḢ

A full program printing a representation of a list of lists.
Works by brute force and is stupidly inefficient.

Try it online! - a 3 by 3, since it is too inefficient to run even a size 4 within the 60 second TIO limit!

How?

FJṁa@µ«Ḋoµ€ZUµ4¡ÐLFQL<3 - Link 1 isConnected? List of lists
...                     - 1 if connected 0 if not -- see linked answer in the header

ḟ0ĠḊ€ - Link 2, helperFor-AnyRepeatedValues: list
ḟ0    - filter out zeros
  Ġ   - group indices by value (i.e. [[indices of min],...,[indices of max]]
   Ḋ€ - dequeue €ach -- leaving a list of empty lists iff no repeated values
      -                 any remaining values are non-zero (1-based indexing in Jelly)

¬T€œ&2\;Ç€FȦ - Link 3, columnwiseAnyAdjacentZerosOrRowwiseAnyRepeatedValues: list of lists
¬            - logical not (convert all zeros to ones and all others to zeros)
 T€          - for €ach row get a list of truthy indexes (i.e. indexes of original zeros)
     2\      - pairwise reduction (i.e. for neighbouring rows) with:
   œ&        -   intersection (empty if no columnwise adjacent original zeros
             -                 any remaining values are non-zero due to 1-based indexing)
        Ç€   - call last link (1) as a monad for €ach row
       ;     - concatenate
          F  - flatten into a single list (empty iff no columnwise adjacent original zeros
             -                                   AND no rowwise repeated values)
           Ȧ - any and all (0 if empty [or contains any zero -- never] else 1)

ZÇȯÇ_1Ŀ - Link 4, validity check? list of lists
Z       - transpose
 Ç      - call last link (2) as a monad rowwiseAnyAdjacentZerosOrColumnwiseAnyRepeatedValues?
   Ç    - call last link (2) as a monad columnwiseAnyAdjacentZerosOrRowwiseAnyRepeatedValues?
  ȯ     - logical OR
     1Ŀ - call link 1 as a monad (isConnected?)
    _   - subtract
        - this yields -1 for valid, while it yields 0 or 1 if not.

2ḶṗLṗLa⁸ÇÞḢ - Main link: list of lists
2Ḷ          - lowered range of 2 -> [0,1]
   L        - length (number of rows in the input)
  ṗ         - Cartesian power (all lists of zeros and ones of length L)
     L      - length (number of rows in the input again)
    ṗ       - Cartesian power (all grids of zeros and ones of same shape as the input)
       ⁸    - the input
      a     - logical AND -- effectively uses each of the formed grids as a mask
         Þ  - sort by:
        Ç   -   last link (3) as a monad
          Ḣ - head
            - implicit print

Answer 3

APL (Dyalog Unicode), 133 bytes^SBCS

{q←{⊢/4 2⍴⍵}⌺3 3⋄g←⍵=⊂∪,⍵⋄⍵×~1⊃{((⌈/q b)⌈b<{2<≢∪0,,(⍵×⊢⌈⌈/∘q)⍣≡⍵×(⍴⍵)⍴1+⍳≢,⍵}¨~b∘⌈¨⊂⍤2∘.≡⍨⍳⍴b)(+/↑w<g×⌈.⌈⍨w×g)⌈w b←⍵}⍣≡×\(⌈/=∘⌽⍨q⍵)0}

Try it online!

My implementation of rule #4 (cells must form a single connected component) is rather wasteful, but still this passes all tests in about 10 seconds on TIO.

---

The overall algorithm: Store two boolean matrices b and w for cells that are certain to be black and white respectively. Initialise b as all-zero. Initialise w as 1 only for those cells that have opposite matching neighbours.

Repeat until b and w settle down:

• add to b cells that are on the same line (horizontal or vertical) and of the same value as a cell in w

• add to w the immediate neighbours of all cells in b

• add to w all cutpoints - cells whose removal would split the graph of non-black cells into multiple connected components

Finally, output not(b) multiplied by the original matrix.