21
\$\begingroup\$

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 , 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

\$\endgroup\$
  • 2
    \$\begingroup\$ I suggest that you require deterministic runtime, or require that the largest test case can be solved in no more than 1 minute (or maybe more/less). Also, you say 4 <= n <= 16, but the largest test case is for n=9. I suggest you either post a n=16 test case, or say 4 <= n <= 9. Nice challenge by the way :) \$\endgroup\$ – Stewie Griffin Jan 29 '18 at 21:35
  • 1
    \$\begingroup\$ @StewieGriffin how about just having a separate fastest algorithm challenge? \$\endgroup\$ – Jonathan Allan Jan 29 '18 at 22:05
  • \$\begingroup\$ @StewieGriffin Tried to add a 16x16 but not yet quite ready. Changed to 9 now. \$\endgroup\$ – Weijun Zhou Jan 29 '18 at 22:35
  • \$\begingroup\$ @JonathanAllan As you wish. \$\endgroup\$ – Weijun Zhou Jan 30 '18 at 15:51
  • \$\begingroup\$ Re "I decide to make a change to see whether it would be better": It would definitely be worse. Also you should not change an already posted challenge. \$\endgroup\$ – user202729 Jan 31 '18 at 8:17
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Thank you. Very impressive. Personally I am a beginner but also a big fan of Haskell. \$\endgroup\$ – Weijun Zhou Feb 3 '18 at 1:08
  • \$\begingroup\$ tio.run/… \$\endgroup\$ – H.PWiz Feb 7 '18 at 19:43
  • 1
    \$\begingroup\$ The above was too many characters too leave a comment alongside. It is just removing some whitespace \$\endgroup\$ – H.PWiz Feb 7 '18 at 19:44
  • 1
    \$\begingroup\$ tio.run/##bVHbbtswDH33V2RIHkiESmvn6jQKNmAvA/… \$\endgroup\$ – Lynn Feb 8 '18 at 13:07
2
+50
\$\begingroup\$

APL (Dyalog Unicode), 133 bytesSBCS

{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.

\$\endgroup\$
  • \$\begingroup\$ Thank you very much for your interest and explanation. I think what you described is also a typical algorithm used if one is to solve the puzzle by hand. \$\endgroup\$ – Weijun Zhou Feb 8 '18 at 11:09
  • 1
    \$\begingroup\$ To be honest, I never even tried to solve Hitori by hand. I got these tricks from Wikipedia and I don't have a proof that the algorithm would always converge all the way to the (unique) solution. \$\endgroup\$ – ngn Feb 8 '18 at 12:29
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ NIce as a start. Thank you. I will take a look. \$\endgroup\$ – Weijun Zhou Jan 29 '18 at 22:34
  • \$\begingroup\$ You forgot the 4th rule. (connected) \$\endgroup\$ – user202729 Jan 30 '18 at 5:23
  • \$\begingroup\$ (good luck with implementing BFS/DFS/DSU in Jelly) \$\endgroup\$ – user202729 Jan 30 '18 at 5:24
  • \$\begingroup\$ Oh... will delete when at a computer. Thanks. \$\endgroup\$ – Jonathan Allan Jan 30 '18 at 7:09
  • \$\begingroup\$ yeah, I don't think this is possible in, say, <60 bytes of Jelly, not to say <100... \$\endgroup\$ – Erik the Outgolfer Jan 30 '18 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.