16
\$\begingroup\$

Inspired by Flow Fit: Sudoku, a brand-new mobile puzzle game (as of Nov 2019).

Background

A Latin square is a square grid of side length \$ n \$ filled with \$ n \$ different symbols, where each row and column contains each symbol exactly once.

Let's define a row (resp. a column) as a maximally consecutive group of cells in horizontal (resp. vertical) direction. For example, the following board (O is a cell, - is a hole) has 8 rows and 8 columns in total:

The board    |  Rows         |  Columns
O O O O O O  |  A A A A A A  |  A B C E G H
O O O O O O  |  B B B B B B  |  A B C E G H
O O - O O O  |  C C - D D D  |  A B - E G H
O O O - O O  |  E E E - F F  |  A B D - G H
O O O O O O  |  G G G G G G  |  A B D F G H
O O O O O O  |  H H H H H H  |  A B D F G H

Then, place the numbers \$ 1, \cdots, k \$ exactly once on each row and column, where \$ k \$ is the length of that row or column. For the board above, here is one solution:

3 4 1 2 5 6
4 3 2 1 6 5
1 2 - 3 1 2
2 1 3 - 2 1
5 6 1 2 3 4
6 5 2 1 4 3

A board is Latin-style if such a placement is possible.

Note that a row/column of size 1 is still a row/column, and therefore it can only have a single 1.

Challenge

Given a grid, determine if it is Latin-style, i.e. it is possible to place numbers on the grid so that each row/column of length \$ k \$ contains each of the numbers \$ 1, \cdots, k \$ exactly once.

Example Latin-style boards

O O O O O
- O O O O
- - O O O
- - - O O
- - - - O

- O O O -
O O O O O
O O O O O
O O O O O
- O O O -

- - O O O
- O O O O
O O O O O
O O O O -
O O O - -

O O - - O O
O O O O O O
- O O O O -
- O O O O -
O O O O O O
O O - - O O

O O O - O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O -
- O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O - O O O

O O O - O
O O - O O
O - O O O

- - O - -
- O O O -
O O - O O
- O O O O
O O O - O

Example non-Latin-style boards

- O -
O O O
- O -

O O O

O O - - -
O O - - -
O O - - -
O O O O O
O O O O O

O O O - -
O O O - -
O O O O O
- - O O O
- - O O O

- - - O O - -
- - O O O - -
O O O O O O -
O O O O O O O
- O O O O O O
- - O O O - -
- - O O - - -

O O - - - -
O O - O O O
O O - O O O

O O - - -
O O - - -
O O O - -
- - O O O
- - O O O

Input and output

You can take the grid input in any reasonable way. The grid's bounding box can be non-square, and the grid may contain multiple connected components.

You can give the output in one of two ways:

  • Truthy/falsy values following the language's convention
    • Swapping truthy/falsy is not allowed also allowed.
  • One consistent value for true, another consistent value for false

Scoring and winning criterion

The standard rules apply. The shortest code in bytes wins.

Improve this question
\$\endgroup\$
5
  • \$\begingroup\$ Just checking, we can use the boolean values False/True as long as they are consistent? \$\endgroup\$
    – Jo King ♦
    Commented Dec 5, 2019 at 9:43
  • 1
    \$\begingroup\$ "Swapping truthy/falsy is not allowed" and "One consistent value for true, another consistent value for false" contradict each other (if I would state I use false as consistent value for true and vice-versa given the second output-option). \$\endgroup\$
    – Kevin Cruijssen
    Commented Dec 5, 2019 at 11:49
  • \$\begingroup\$ @NickKennedy I just removed the restriction. \$\endgroup\$
    – Bubbler
    Commented Dec 5, 2019 at 13:53
  • \$\begingroup\$ Brute force approaches would likely timeout on the larger test cases... is that ok? \$\endgroup\$
    – Jonah
    Commented Dec 5, 2019 at 17:53
  • 1
    \$\begingroup\$ @Jonah It's absolutely fine, as always. \$\endgroup\$
    – Bubbler
    Commented Dec 5, 2019 at 22:20

3 Answers 3

Reset to default
6
\$\begingroup\$

Jelly, 24 bytes

,ZµŒgaS$€F)Zṣ€0Ṣ<JƊ€€)FẸ

Try it online!

A monadic link taking as its argument the grid as a matrix with 1 representing squares needing a number and 0 representing the spacers. Returns 0 if the grid is Latin and 1 if not.

Explanation

Main link, takes a matrix of 1s and 0s as its argument, z

,                         | Pair with:
 Z                        | - z transposed
  µ                       | Start a new monadic chain
                     )    | For each matrix (z and transpose(z)):
          )               | - For each row:
   Œg                     |   - Group runs of equal elements
       $€                 |   - For each group:
     a                    |     - And with:
      S                   |       - Sum of group
         F                |   - Flatten
           Z              | - Transpose
            ṣ€0           | - Split each at zeros
                  Ɗ€€     | - For each group:
               Ṣ<         |   - Check whether sorted group is less than:
                 J        |     - Sequence along group
                      F   | Finally, flatten
                       Ẹ  | And check if any group returned true

Alternative in case true=true/false=false required:

Jelly, 24 bytes

,ZµŒgaS$€F)Zṣ€0Ṣ_JƊ€€)AƑ

Try it online!

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ This program (along with the R port) gives the wrong answer for O O - - - / O O - - - / O O O - - / - - O O O / - - O O O. \$\endgroup\$
    – Nitrodon
    Commented Dec 11, 2019 at 17:59
3
\$\begingroup\$

Prolog (SWI) + CLPFD, 192 bytes

A/B:-transpose(A,B).
[]*[]*_*1*_.
[0|T]*[0|B]*_*1*_:-T*B*L*L*[].
[1|T]*[A|B]*L*C*Z:-all_distinct([A|Z]),A#>0,A#<L,R#=C-1,T*B*L*R*[A|Z].
[]-[].
[X|T]-[Y|B]:-X*Y*L*L*[],T-B.
+A:-A-B,A/T,B/U,T-U.

Try it online!

The main predicate is +/1.

Verbose

t(A,B):-transpose(A,B).
h([],[],_,1,_).
h([0|T],[0|B],_,1,_):-h(T,B,L,L,[]).
h([1|T],[A|B],L,C,Z):-all_distinct([A|Z]),A#>0,A#<L,R#=C-1,h(T,B,L,R,[A|Z]).
q([],[]). q([X|T],[Y|B]):-h(X,Y,L,L,[]),q(T,B).
g(A):-q(A,B),t(A,T),t(B,U),q(T,U).

Try it online!

g/1 takes the grid as a list of lists, each element being a 1 for a cell or a 0 for a hole. q/2 takes a grid as the first argument and unifies the second argument with a solution of the grid. h(A,B,L,L,[]) takes a row of this grid as A, and unifies a solution for the row to B, and q/2 recursively calls h/5 on each of its rows.

h(A,B,L,C,Z) has row A of the grid, a solution B, L is the length of the current length of 1s plus one so that the cells of B can be constrained to the exclusive range (1, L), C is the count of the remaining length so that L is unified to the length, and Z is the solution for the current contiguous sequence of cells so that all_distinct/2 can be called. The end cases are stated as conditions so that these constraints are fulfilled.

Because this is Prolog, converting the main predicate to take two arguments, like A+B or g(A,B), Prolog will unify the solutions with the variable B, thus also allowing you to see all available solutions. It can also generate valid grids, but running this makes Prolog list all grids with empty rows.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

R, 169 bytes

function(x)any(unlist(lapply(1:2,function(m)apply(apply(x,m,function(y,r=rle(y))rep(r$l*r$v,r$l)),1,function(a)tapply(a,cumsum(!a),function(d)sort(e<-d[!!d])<seq(e))))))

Try it online!

An R translation of my Jelly answer. I’m not sure it’s much easier to follow! Takes a matrix of 0s and 1s and returns a logical scalar (FALSE if Latin, TRUE if not). Note because of the way base R tends to collapse matrices to vectors, the input has to have at least 2 rows and columns, but this can be done by padding input with an extra row or column of FALSEs. If this is unacceptable, I can work around it at the cost of extra bytes to handle the edge case.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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