perplexus.info :: Logic : No repeated numbers

No repeated numbers (Posted on 2008-08-20)

Look at the 8x8 grid below at left. In the rows and columns there are repeated numbers. Erasing 19 of them, we achieve the grid at right, that has no repeated numbers in any row, in any column.

+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| 5 | 7 | 1 | 2 | 5 | 4 | 4 | 3 |       |   | 7 | 1 |   | 5 |   | 4 | 3 |
+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| 4 | 3 | 1 | 2 | 7 | 5 | 6 | 3 |       | 4 | 3 |   | 2 | 7 | 5 | 6 |   |
+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| 5 | 5 | 3 | 4 | 2 | 1 | 7 | 8 |       |   | 5 | 3 |   | 2 |   | 7 | 8 |
+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| 6 | 6 | 2 | 7 | 3 | 3 | 3 | 1 |       | 6 |   | 2 | 7 |   | 3 |   | 1 |
+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| 3 | 2 | 5 | 6 | 9 | 1 | 8 | 6 |       | 3 | 2 | 5 |   | 9 | 1 | 8 | 6 |
+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| 2 | 1 | 3 | 4 | 6 | 2 | 5 | 2 |       |   | 1 |   | 4 | 6 |   | 5 | 2 |
+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| 9 | 8 | 4 | 1 | 4 | 6 | 2 | 3 |       | 9 | 8 | 4 | 1 |   | 6 | 2 |   |
+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| 7 | 5 | 6 | 5 | 8 | 5 | 1 | 4 |       | 7 |   | 6 | 5 | 8 |   | 1 | 4 |
+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+

Do the same with this 8x8 grid, erasing the minimum number of squares.

                    +---+---+---+---+---+---+---+---+
                    | 8 | 4 | 6 | 5 | 3 | 5 | 7 | 4 |
                    +---+---+---+---+---+---+---+---+
                    | 6 | 5 | 5 | 4 | 7 | 8 | 3 | 1 |
                    +---+---+---+---+---+---+---+---+ 
                    | 5 | 7 | 2 | 5 | 5 | 4 | 8 | 7 |
                    +---+---+---+---+---+---+---+---+
                    | 8 | 6 | 5 | 3 | 2 | 5 | 4 | 4 |
                    +---+---+---+---+---+---+---+---+
                    | 3 | 8 | 1 | 4 | 8 | 6 | 5 | 2 |
                    +---+---+---+---+---+---+---+---+ 
                    | 5 | 3 | 7 | 6 | 4 | 2 | 2 | 2 |
                    +---+---+---+---+---+---+---+---+
                    | 5 | 8 | 7 | 7 | 6 | 2 | 1 | 3 |
                    +---+---+---+---+---+---+---+---+
                    | 1 | 1 | 3 | 7 | 6 | 4 | 6 | 8 |
                    +---+---+---+---+---+---+---+---+

See The Solution Submitted by pcbouhid

Rating: 4.0000 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

2880 solutions; 6 Hitori

| Comment 18 of 20 |

For the minimum 19 removals altogether:

There are 2 ways of choosing the minimum one occurrence of the digit 1.

There is only one valid way of choosing the minimum of two occurrences of the digit 2.

No 3's need be removed.

There are twelve ways of validly removing the four 4's that need removal.

There are ten ways of validly removing the six 5's needing removal.

There's only one way of removing the only 6 needing removal.

There are six ways of removing the three 7's needing removal.

There are two ways of removing the two 8's to be removed.

No 9's need removal.

That makes 2*1*12*10*1*6*2 = 2880 ways of combining these into a solution to the problem as posed.

Here are the possible remaining positions after the removals, by digit:

........ ........
.......1 .......1
........ ........
........ ........
..1..... ..1.....
........ ........
......1. ......1.
1....... .1......


........
........
..2.....
....2...
.......2
......2.
.....2..
........


.4...... .4...... .4...... .4...... .4...... .4......
...4.... ...4.... ........ ........ ...4.... ...4....
.....4.. ........ .....4.. ........ .....4.. ........
......4. ......4. ......4. ......4. .......4 .......4
........ ........ ...4.... ...4.... ........ ........
....4... ....4... ....4... ....4... ....4... ....4...
........ ........ ........ ........ ........ ........
........ .....4.. ........ .....4.. ........ .....4..

.4...... .4...... .......4 .......4 .......4 .......4
........ ........ ...4.... ...4.... ........ ........
.....4.. ........ .....4.. ........ .....4.. ........
.......4 .......4 ......4. ......4. ......4. ......4.
...4.... ...4.... ........ ........ ...4.... ...4....
....4... ....4... ....4... ....4... ....4... ....4...
........ ........ ........ ........ ........ ........
........ .....4.. ........ .....4.. ........ .....4..


...5.... ...5.... ...5.... ...5.... ...5....
.5...... .5...... .5...... .5...... ..5.....
....5... ....5... ....5... ....5... ....5...
..5..... ..5..... .....5.. .....5.. .....5..
......5. ......5. ......5. ......5. ......5.
5....... ........ 5....... ........ 5.......
........ 5....... ........ 5....... ........
........ ........ ........ ........ ........

...5.... .....5.. .....5.. .....5.. .....5..
..5..... .5...... .5...... .5...... .5......
....5... ...5.... ...5.... ....5... ....5...
.....5.. ..5..... ..5..... ..5..... ..5.....
......5. ......5. ......5. ......5. ......5.
........ 5....... ........ 5....... ........
5....... ........ 5....... ........ 5.......
........ ........ ........ ........ ........


..6.....
6.......
........
.6......
.....6..
...6....
....6...
......6.


......7. ......7. ......7. ......7. ......7. ......7.
....7... ....7... ....7... ....7... ....7... ....7...
.7...... .7...... .7...... .......7 .......7 .......7
........ ........ ........ ........ ........ ........
........ ........ ........ ........ ........ ........
..7..... ........ ..7..... ..7..... ........ ..7.....
........ ..7..... ...7.... ........ ..7..... ...7....
...7.... ...7.... ........ ...7.... ...7.... ........


8....... ........
.....8.. .....8..
......8. ......8.
........ 8.......
....8... ....8...
........ ........
.8...... .8......
.......8 .......8

Of the 2880 ways of combining these, only 6 are Hitori in the sense defined in previous comments, of having no two blanks adjacent horizontally or vertically. However, I see that both restrictions actually apply, and none of these is a Hitori, as there are islands, digits not connected to the others. So these are pseudo-Hitori.

  4 6 5 3   7
6 5   4 7 8 3 1
  7 2   5   8
8 6   3 2 5   4
3   1   8 6 5 2
5 3   6 4   2
  8 7   6 2 1 3
1   3 7   4 6 8

  4 6 5 3   7
6 5   4 7 8 3 1
  7 2   5   8
8 6   3 2 5   4
3   1   8 6 5 2
  3   6 4   2
5 8 7   6 2 1 3
1   3 7   4 6 8

  4 6 5 3   7
6   5 4 7 8 3 1
  7 2   5   8
8 6   3 2 5   4
3   1   8 6 5 2
5 3   6 4   2
  8 7   6 2 1 3
1   3 7   4 6 8

  4 6 5 3   7
6   5 4 7 8 3 1
  7 2   5   8
8 6   3 2 5   4
3   1   8 6 5 2
  3   6 4   2
5 8 7   6 2 1 3
1   3 7   4 6 8

  4 6 5 3   7
6 5   4 7 8 3 1
  7 2   5   8
8 6   3 2 5   4
3   1   8 6 5 2
  3   6 4   2
5 8 7   6 2 1 3
  1 3 7   4 6 8
  
  4 6 5 3   7
6   5 4 7 8 3 1
  7 2   5   8
8 6   3 2 5   4
3   1   8 6 5 2
  3   6 4   2
5 8 7   6 2 1 3
  1 3 7   4 6 8

 6             2880

The last line verifies the count of 6 pseudo-Hitori, and having considered all 2880 configurations of solutions.

DECLARE SUB takeEm (d!)
DIM SHARED b$(8), hit$(8), conCt, solCt

DATA      84653574
DATA      65547831
DATA      57255487
DATA      86532544
DATA      38148652
DATA      53764222
DATA      58776213
DATA      11376468

FOR i = 1 TO 8
READ b$(i)
b$(i) = LTRIM$(RTRIM$(b$(i)))
hit$(i) = b$(i)
NEXT

DIM SHARED sol$(9, 12, 8), noSolns(9)

OPEN "noreptno.txt" FOR INPUT AS #1

DO
chk$ = ""

FOR i = 1 TO 9
LINE INPUT #1, s$(i)
chk$ = chk$ + s$(i)
NEXT i
FOR i = 1 TO 9
d$ = LTRIM$(STR$(i))
IF INSTR(chk$, d$) > 0 THEN EXIT FOR
NEXT i
dig = VAL(d$)
IF dig <> prevDig THEN noSolns(prevDig) = solNo: solNo = 0
solNo = solNo + 1
FOR i = 1 TO 8
sol$(dig, solNo, i) = s$(i)
NEXT

prevDig = dig
LOOP UNTIL EOF(1)
noSolns(prevDig) = solNo

takeEm 1
CLOSE
PRINT solCt, conCt

SUB takeEm (d)
c$ = LTRIM$(STR$(d))
FOR sol = 1 TO noSolns(d)
   FOR i = 1 TO 8
    FOR j = 1 TO 8
      IF MID$(b$(i), j, 1) = c$ THEN
       IF MID$(sol$(d, sol, i), j, 1) = "." THEN
        MID$(hit$(i), j, 1) = " "
       END IF
      END IF
    NEXT
   NEXT

   SELECT CASE d
    CASE 2
     takeEm 4
    CASE 8
     conCt = conCt + 1
     good = 1
     FOR i = 1 TO 8
      IF INSTR(hit$(i), " ") THEN good = 0: EXIT FOR
     NEXT
     IF good THEN
      FOR i = 1 TO 7
       FOR j = 1 TO 8
         IF MID$(hit$(i), j, 1) = " " AND MID$(hit$(i + 1), j, 1) = " " THEN good = 0: EXIT FOR
       NEXT
       IF good = 0 THEN EXIT FOR
      NEXT
      IF good THEN
       solCt = solCt + 1
       FOR i = 1 TO 8
        FOR j = 1 TO 8
         PRINT MID$(hit$(i), j, 1); " ";
        NEXT
        PRINT
       NEXT
       PRINT
       DO: LOOP UNTIL INKEY$ > ""
      END IF
     END IF
    CASE ELSE
     takeEm d + 1
   END SELECT

   FOR i = 1 TO 8
    FOR j = 1 TO 8
      IF MID$(b$(i), j, 1) = c$ THEN
       MID$(hit$(i), j, 1) = c$
      END IF
    NEXT
   NEXT

NEXT
END SUB

Editing corrected mislabeling these "pseudo-Hitori" as Hitori.

Edited on August 24, 2008, 1:18 pm

Posted by Charlie on 2008-08-24 13:10:41

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info