Product puzzle

Probability Level 3

Write a single positive digit $(\leq 6)$ into each empty square in the figure below, such that every number $(1, 2, 3, 4, 5, 6)$ appears in each row and in each column. The number in a circle shows the product of the four numbers around it.

If you are finished, find the minimum value of the product of the numbers in the pink squares!

Note: Here is a sample, with digits $1, 2, 3, 4$ :

The answer is 20.

2 solutions

Áron Bán-Szabó
Aug 20, 2017

How did you get this configuration? Is this configuration unique?

Pi Han Goh - 3 years, 9 months ago

Using logic :)

Mostly I used two type of step:

1) Consider a row or column, and you want to find, where will be the number x. For example: In this row, the number 6 can't be here, because in that column, there is already a 6. Or an other example: In this column the number 5 can't be here, because 90 is not a multiply of 5.

2) Maths and prime factors...

And yes, this is the unique solution.

Áron Bán-Szabó - 3 years, 9 months ago

Ervin Varga
Jul 2, 2020

Below is my Java program that solves this puzzle. I use puzzles for teaching students about backtracking and how computers can solve these sort of problems blazingly fast. Below the program you can also see the output from running it.

public class ProductPuzzle {
    private static final int BOARD_SIZE = 6;
    private int[][] board;

    private boolean isValidProductBlock(int row, int col, int value) {
        if (board[row][col] * board[row][col + 1] * board[row + 1][col] * board[row + 1][col + 1] != 0)
            return board[row][col] * board[row][col + 1] * board[row + 1][col] * board[row + 1][col + 1] == value;
        else return true;
    }

    public boolean areDigitsDistinct() {
        final var columnMarkers = new boolean[BOARD_SIZE][BOARD_SIZE];

        for (var row = 0; row < BOARD_SIZE; row++) {
            var rowMarkers = new boolean[BOARD_SIZE];
            for (var col = 0; col < BOARD_SIZE; col++) {
                var cell = board[row][col];
                if (cell > 0) {
                    cell--;
                    if (rowMarkers[cell] || columnMarkers[col][cell]) return false;
                    rowMarkers[cell] = columnMarkers[col][cell] = true;
                }
            }
        }

        return true;
    }

    private boolean isValidBoard() {
        return areDigitsDistinct() &&
                isValidProductBlock(0, 2, 60) &&
                isValidProductBlock(0, 4, 240) &&
                isValidProductBlock(1, 0, 90) &&
                isValidProductBlock(1, 3, 32) &&
                isValidProductBlock(2, 1, 60) &&
                isValidProductBlock(2, 4, 24) &&
                isValidProductBlock(3, 0, 40) &&
                isValidProductBlock(3, 2, 36) &&
                isValidProductBlock(4, 1, 144) &&
                isValidProductBlock(4, 4, 90);
    }

    private boolean backtrack(int row, int col) {
        if (col == BOARD_SIZE) {
            col = 0;
            row++;
        }

        // We are done when we have filled all cells.
        if (row == BOARD_SIZE) return true;

        for (var number = 1; number <= BOARD_SIZE; number++) {
            board[row][col] = number;
            if (isValidBoard() && backtrack(row, col + 1)) return true;
            board[row][col] = 0;
        }

        return false;
    }

    private static void print2DArray(int[][] a) {
        for (int i = 0; i < a.length; ++i) {
            for (int j = 0; a[i] != null && j < a[i].length; ++j) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }

    public void solveProductPuzzle() {
        board = new int[BOARD_SIZE][BOARD_SIZE];
        backtrack(0, 0);
        print2DArray(board);
    }

    public static void main(String[] args) {
        new ProductPuzzle().solveProductPuzzle();
    }
}

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

Product puzzle

The answer is 20.

2 solutions

0 pending reports