Views
From CSULA CS Wiki
Like the previous version, this one extends the solution cell-by-cell. It uses the techniques suggested in the homework assignment.
Here are traces of three runs: a 4x4, a 5x5, and an 8x8.
Contents |
Explanation
This example is taken from the 4x4 problem below.
At each step a partial solution like the following is printed.
3 4 1 2
_ _ _ _
_ _ _ _
_ _ _ _
Open cells: 12
(2,1) -> [2,4]
3 4 1 2
2 _ _ _
_ _ _ _
_ _ _ _
Queue length: 1
The solver keeps an ordered queue of partial solutions. It expands the one that has the most constrained cell. (If multiple partial solutions are tied for most constrained cell, the one with the fewest open cells is selected. If there are multiple of these, one is selected arbitrarily.)
The trace shows the partial solution before and after instantiating a cell. A reference to the cell being instantiated is shown in the middle pointing to a list of possible values. (In this case cell (2, 1) can be instantiated to either 2 or 4.) In many cases only one value is possible. But if two values are listed, the partial solution is split into two and both are created.
Partial solutions are inserted into a queue of partial solutions at the spot that corresponds to the constraint on their most constrained cells after the instantiation of the current one. Once a cell is instantiated, the other cells become more constrained making it likely that those expanded grids will appear near the front of the queue.
If no values are possible this is shown.
3 1 4 2 _ _ _ _ 1 _ _ 3 _ _ _ _ Open cells: 10 (3,3) -> [] Dead end
This is a dead end of the 4x4. (It is also shown in the 4x4 section immediately below.) It's a dead end because the 12x cage must be either [1, 3, 4] (in some order) or [2, 3, 2]. No permutation of [1, 3, 4] is possible since 1, 3, or 4 would have to be placed in (3, 3). But that's not possible because both 1 and 3 already appear in row 3 and 4 appears in column 3.
[2, 3, 2] is not possible because if 2 is put in (3, 3), there are no possible values to put into (3, 2) that will satisfy the 3+ cage at the start of row 3.
How does the solver know all this? It keeps track of the candidate values for each cell. Once 1 and 3 are placed in row 3 and 4 is placed in column 3, the only remaining candidate for (3, 3) is 2.
But the solver also pre-computes all possible cage values. It then eliminates the ones that are in conflict with existing decisions. After putting 1 in (3, 1) the only remaining cage combination for the 3+ cage at the start of row 3 is [1, 2]. But if we put a 2 in (3, 3) that cage combination is no longer possible, eliminating the possibility of putting 2 in (3, 3). Hence the dead end.
Code and example files
- "KenKen" (zip) (upload page)
Load the files by loading ExampleKenKens. It will import KenKen, the KenKen solver.
A 4x4 example
kk4 = [ Cage 1 Subtract [(1, 1), (2, 1)]
, Cage 3 Subtract [(1, 2), (1, 3)]
, Cage 2 Divide [(1, 4), (2, 4)]
, Cage 12 Multiply [(2, 2), (2, 3), (3, 3)]
, Cage 3 Add [(3, 1), (3, 2)]
, Cage 4 Add [(3, 4), (4, 4)]
, Cage 24 Multiply [(4, 1), (4, 2), (4, 3)]
]
3 4 1 2
2 1 3 4
1 2 4 3
4 3 2 1
> solveKenKen kk4 [1 .. ] -- Trace when the number of empty cells is in [1 .. ],
-- i.e., all the time.
_ _ _ _
_ _ _ _
_ _ _ _
_ _ _ _
Open cells: 16
(1,2) -> [1,4]
_ 1 _ _ -- This is one of the possibilities for this cell. The other
_ _ _ _ -- possibility — i.e., 4 in (1, 2) — goes into the queue.
_ _ _ _ -- This decision leads directly to a contradiction and will be withdrawn.
_ _ _ _ -- From here on until the dead end, all moves are forced, i.e., each
Queue length: 1 -- cell considered has only one possible value. Can you see why?
_ 1 _ _
_ _ _ _
_ _ _ _
_ _ _ _
Open cells: 15
(1,3) -> [4]
_ 1 4 _
_ _ _ _
_ _ _ _
_ _ _ _
Queue length: 1
_ 1 4 _
_ _ _ _
_ _ _ _
_ _ _ _
Open cells: 14
(1,4) -> [2]
_ 1 4 2
_ _ _ _
_ _ _ _
_ _ _ _
Queue length: 1
_ 1 4 2
_ _ _ _
_ _ _ _
_ _ _ _
Open cells: 13
(1,1) -> [3]
3 1 4 2
_ _ _ _
_ _ _ _
_ _ _ _
Queue length: 1
3 1 4 2
_ _ _ _
_ _ _ _
_ _ _ _
Open cells: 12
(3,1) -> [1]
3 1 4 2
_ _ _ _
1 _ _ _
_ _ _ _
Queue length: 1
3 1 4 2
_ _ _ _
1 _ _ _
_ _ _ _
Open cells: 11
(3,4) -> [3]
3 1 4 2
_ _ _ _
1 _ _ 3
_ _ _ _
Queue length: 1
3 1 4 2
_ _ _ _
1 _ _ 3
_ _ _ _
Open cells: 10
(3,3) -> [] -- Given the other cell values, no value can be put into (3, 3).
Dead end -- The partial solution with 1 in (1, 2) has reached a dead end.
_ 4 _ _ -- Continue with the partial solution with 4 in (1, 2).
_ _ _ _ -- This is the partial solution that was in the queue.
_ _ _ _ -- The queue is now empty.
_ _ _ _
Open cells: 15
(1,3) -> [1]
_ 4 1 _
_ _ _ _
_ _ _ _
_ _ _ _
Queue length: 0
_ 4 1 _
_ _ _ _
_ _ _ _
_ _ _ _
Open cells: 14
(1,4) -> [2]
_ 4 1 2
_ _ _ _
_ _ _ _
_ _ _ _
Queue length: 0
_ 4 1 2
_ _ _ _
_ _ _ _
_ _ _ _
Open cells: 13
(1,1) -> [3]
3 4 1 2
_ _ _ _
_ _ _ _
_ _ _ _
Queue length: 0
3 4 1 2
_ _ _ _
_ _ _ _
_ _ _ _
Open cells: 12
(2,1) -> [2,4] -- Here again there are two choices.
3 4 1 2
2 _ _ _ -- It turns out that putting 2 in (1, 2) is the right choice.
_ _ _ _ -- The other choice goes into the queue—and will remain there.
_ _ _ _ -- Fronm here on, all the moves are forced—and the puzzle is solved.
Queue length: 1
3 4 1 2
2 _ _ _
_ _ _ _
_ _ _ _
Open cells: 11
(3,1) -> [1]
3 4 1 2
2 _ _ _
1 _ _ _
_ _ _ _
Queue length: 1
3 4 1 2
2 _ _ _
1 _ _ _
_ _ _ _
Open cells: 10
(4,1) -> [4]
3 4 1 2
2 _ _ _
1 _ _ _
4 _ _ _
Queue length: 1
3 4 1 2
2 _ _ _
1 _ _ _
4 _ _ _
Open cells: 9
(3,2) -> [2]
3 4 1 2
2 _ _ _
1 2 _ _
4 _ _ _
Queue length: 1
3 4 1 2
2 _ _ _
1 2 _ _
4 _ _ _
Open cells: 8
(3,4) -> [3]
3 4 1 2
2 _ _ _
1 2 _ 3
4 _ _ _
Queue length: 1
3 4 1 2
2 _ _ _
1 2 _ 3
4 _ _ _
Open cells: 7
(3,3) -> [4]
3 4 1 2
2 _ _ _
1 2 4 3
4 _ _ _
Queue length: 1
3 4 1 2
2 _ _ _
1 2 4 3
4 _ _ _
Open cells: 6
(2,3) -> [3]
3 4 1 2
2 _ 3 _
1 2 4 3
4 _ _ _
Queue length: 1
3 4 1 2
2 _ 3 _
1 2 4 3
4 _ _ _
Open cells: 5
(2,2) -> [1]
3 4 1 2
2 1 3 _
1 2 4 3
4 _ _ _
Queue length: 1
3 4 1 2
2 1 3 _
1 2 4 3
4 _ _ _
Open cells: 4
(2,4) -> [4]
3 4 1 2
2 1 3 4
1 2 4 3
4 _ _ _
Queue length: 1
3 4 1 2
2 1 3 4
1 2 4 3
4 _ _ _
Open cells: 3
(4,2) -> [3]
3 4 1 2
2 1 3 4
1 2 4 3
4 3 _ _
Queue length: 1
3 4 1 2
2 1 3 4
1 2 4 3
4 3 _ _
Open cells: 2
(4,3) -> [2]
3 4 1 2
2 1 3 4
1 2 4 3
4 3 2 _
Queue length: 1
3 4 1 2
2 1 3 4
1 2 4 3
4 3 2 _
Open cells: 1
(4,4) -> [1]
3 4 1 2
2 1 3 4
1 2 4 3
4 3 2 1
Queue length: 1
3 4 1 2
2 1 3 4
1 2 4 3
4 3 2 1
4x4 with a new heuristic and no guesses
In the same 4x4 puzzle (to the right), we know that the 3- cage in the top row is either [1, 4] or [4, 1]. That implies that both 1 and 4 are taken—even though we don't know which order is correct. Since 2 and 3 are the only remaining values for the top row, one most go in (1, 1) and the other in (1, 4). But there are no combinations for the 2divide cage that includes a 3. So [1, 4] must be 2 and (1, 1) must be 3.
The previous solution didn't have this strategy. This one does. With this new heuristic, all the moves are forced.
kk4 = [ Cage 1 Subtract [(1, 1), (2, 1)]
, Cage 3 Subtract [(1, 2), (1, 3)]
, Cage 2 Divide [(1, 4), (2, 4)]
, Cage 12 Multiply [(2, 2), (2, 3), (3, 3)]
, Cage 3 Add [(3, 1), (3, 2)]
, Cage 4 Add [(3, 4), (4, 4)]
, Cage 24 Multiply [(4, 1), (4, 2), (4, 3)]
]
3 4 1 2
2 1 3 4
1 2 4 3
4 3 2 1
This version of the trace only shows the after state for each move, not the before state.
> solveKenKen kk4 [1 ..]
Open cells: 16
(3,4) -> [3] -- How was it able to conclude that cell (3, 4) must be a 3?
. . . . -- The 3+ cage in row 3 must be 1 and 2 in some order. So (3, 4)
. . . . -- must be either 3 or 4. But there are no combinations for the
. . . 3 -- 4+ cage at the far right of rows 3 and 4 that has 4 in (3, 4).
. . . . -- So (3, 4) must be 3.
Queue length: 0
Open cells: 15
(4,4) -> [1]
. . . .
. . . .
. . . 3
. . . 1
Queue length: 0
Open cells: 14
(1,4) -> [2]
. . . 2
. . . .
. . . 3
. . . 1
Queue length: 0
Open cells: 13
(2,4) -> [4]
. . . 2
. . . 4
. . . 3
. . . 1
Queue length: 0
Open cells: 12
(1,1) -> [3]
3 . . 2
. . . 4
. . . 3
. . . 1
Queue length: 0
Open cells: 11
(3,3) -> [4]
3 . . 2
. . . 4
. . 4 3
. . . 1
Queue length: 0
Open cells: 10
(1,3) -> [1]
3 . 1 2
. . . 4
. . 4 3
. . . 1
Queue length: 0
Open cells: 9
(1,2) -> [4]
3 4 1 2
. . . 4
. . 4 3
. . . 1
Queue length: 0
Open cells: 8
(2,3) -> [3]
3 4 1 2
. . 3 4
. . 4 3
. . . 1
Queue length: 0
Open cells: 7
(4,3) -> [2]
3 4 1 2
. . 3 4
. . 4 3
. . 2 1
Queue length: 0
Open cells: 6
(4,1) -> [4]
3 4 1 2
. . 3 4
. . 4 3
4 . 2 1
Queue length: 0
Open cells: 5
(4,2) -> [3]
3 4 1 2
. . 3 4
. . 4 3
4 3 2 1
Queue length: 0
Open cells: 4
(2,1) -> [2]
3 4 1 2
2 . 3 4
. . 4 3
4 3 2 1
Queue length: 0
Open cells: 3
(2,2) -> [1]
3 4 1 2
2 1 3 4
. . 4 3
4 3 2 1
Queue length: 0
Open cells: 2
(3,1) -> [1]
3 4 1 2
2 1 3 4
1 . 4 3
4 3 2 1
Queue length: 0
Open cells: 1
(3,2) -> [2]
3 4 1 2
2 1 3 4
1 2 4 3
4 3 2 1
Queue length: 0
3 4 1 2
2 1 3 4
1 2 4 3
4 3 2 1
A 5x5 example with no guesses
How did it figure out the first move?
The only possibilities for the 75* cage are 3, 5, and 5 in some order. But since the two fives can't be in either the same row or column, the three cells must be 5, 3, 5 in (4, 3), (5, 3), and (5, 4) respectively. That leaves 1, 2, and 4 for the rest of column 3.
Since 3 is already committed in column 3, there is no combination of values that satisfies the 48* cage that doesn't have 4 in (3, 3). Hence the first move. That also establishes the 48* cage as 4, 3, 4 in (3, 3), (3, 4), and (4, 4) respectively.
kk5 = [ Cage 2 Subtract [(1, 1), (1, 2)]
, Cage 2 Divide [(1, 3), (1, 4)]
, Cage 9 Add [(1, 5), (2, 4), (2, 5)]
, Cage 24 Multiply [(2, 1), (3, 1), (4, 1)]
, Cage 4 Subtract [(2, 2), (2, 3)]
, Cage 2 Divide [(3, 2), (4, 2)]
, Cage 48 Multiply [(3, 3), (3, 4), (4, 4)]
, Cage 4 Subtract [(3, 5), (4, 5)]
, Cage 75 Multiply [(4, 3), (5, 3), (5, 4)]
, Cage 3 Subtract [(5, 1), (5, 2)]
, Cage 2 Add [(5, 5)]
]
5 3 2 1 4
4 5 1 2 3
2 1 4 3 5
3 2 5 4 1
1 4 3 5 2
> solveKenKen kk5 [1 .. ]
Open cells: 25
(3,3) -> [4]
. . . . .
. . . . .
. . 4 . .
. . . . .
. . . . .
Queue length: 0
Open cells: 24
(3,4) -> [3]
. . . . .
. . . . .
. . 4 3 .
. . . . .
. . . . .
Queue length: 0
Open cells: 23
(4,3) -> [5]
. . . . .
. . . . .
. . 4 3 .
. . 5 . .
. . . . .
Queue length: 0
Open cells: 22
(2,3) -> [1]
. . . . .
. . 1 . .
. . 4 3 .
. . 5 . .
. . . . .
Queue length: 0
Open cells: 21
(2,2) -> [5]
. . . . .
. 5 1 . .
. . 4 3 .
. . 5 . .
. . . . .
Queue length: 0
Open cells: 20
(4,4) -> [4]
. . . . .
. 5 1 . .
. . 4 3 .
. . 5 4 .
. . . . .
Queue length: 0
Open cells: 19
(1,3) -> [2]
. . 2 . .
. 5 1 . .
. . 4 3 .
. . 5 4 .
. . . . .
Queue length: 0
Open cells: 18
(1,4) -> [1]
. . 2 1 .
. 5 1 . .
. . 4 3 .
. . 5 4 .
. . . . .
Queue length: 0
Open cells: 17
(1,1) -> [5]
5 . 2 1 .
. 5 1 . .
. . 4 3 .
. . 5 4 .
. . . . .
Queue length: 0
Open cells: 16
(3,1) -> [2]
5 . 2 1 .
. 5 1 . .
2 . 4 3 .
. . 5 4 .
. . . . .
Queue length: 0
Open cells: 15
(3,2) -> [1]
5 . 2 1 .
. 5 1 . .
2 1 4 3 .
. . 5 4 .
. . . . .
Queue length: 0
Open cells: 14
(3,5) -> [5]
5 . 2 1 .
. 5 1 . .
2 1 4 3 5
. . 5 4 .
. . . . .
Queue length: 0
Open cells: 13
(4,1) -> [3]
5 . 2 1 .
. 5 1 . .
2 1 4 3 5
3 . 5 4 .
. . . . .
Queue length: 0
Open cells: 12
(2,1) -> [4]
5 . 2 1 .
4 5 1 . .
2 1 4 3 5
3 . 5 4 .
. . . . .
Queue length: 0
Open cells: 11
(2,4) -> [2]
5 . 2 1 .
4 5 1 2 .
2 1 4 3 5
3 . 5 4 .
. . . . .
Queue length: 0
Open cells: 10
(2,5) -> [3]
5 . 2 1 .
4 5 1 2 3
2 1 4 3 5
3 . 5 4 .
. . . . .
Queue length: 0
Open cells: 9
(1,5) -> [4]
5 . 2 1 4
4 5 1 2 3
2 1 4 3 5
3 . 5 4 .
. . . . .
Queue length: 0
Open cells: 8
(1,2) -> [3]
5 3 2 1 4
4 5 1 2 3
2 1 4 3 5
3 . 5 4 .
. . . . .
Queue length: 0
Open cells: 7
(4,2) -> [2]
5 3 2 1 4
4 5 1 2 3
2 1 4 3 5
3 2 5 4 .
. . . . .
Queue length: 0
Open cells: 6
(4,5) -> [1]
5 3 2 1 4
4 5 1 2 3
2 1 4 3 5
3 2 5 4 1
. . . . .
Queue length: 0
Open cells: 5
(5,1) -> [1]
5 3 2 1 4
4 5 1 2 3
2 1 4 3 5
3 2 5 4 1
1 . . . .
Queue length: 0
Open cells: 4
(5,2) -> [4]
5 3 2 1 4
4 5 1 2 3
2 1 4 3 5
3 2 5 4 1
1 4 . . .
Queue length: 0
Open cells: 3
(5,3) -> [3]
5 3 2 1 4
4 5 1 2 3
2 1 4 3 5
3 2 5 4 1
1 4 3 . .
Queue length: 0
Open cells: 2
(5,4) -> [5]
5 3 2 1 4
4 5 1 2 3
2 1 4 3 5
3 2 5 4 1
1 4 3 5 .
Queue length: 0
Open cells: 1
(5,5) -> [2]
5 3 2 1 4
4 5 1 2 3
2 1 4 3 5
3 2 5 4 1
1 4 3 5 2
Queue length: 0
5 3 2 1 4
4 5 1 2 3
2 1 4 3 5
3 2 5 4 1
1 4 3 5 2
An 6x6 example with no guesses
kk6 = [ Cage 9 Add [(1, 1), (1, 2)]
, Cage 3 Multiply [(1, 3), (1, 4), (2, 4)]
, Cage 3 Divide [(1, 5), (1, 6)]
, Cage 3 Add [(2, 1), (3, 1)]
, Cage 540 Multiply [(2, 2), (2, 3), (3, 2), (3, 3)]
, Cage 9 Add [(2, 5), (2, 6)]
, Cage 2 Divide [(3, 4), (3, 5)]
, Cage 8 Add [(3, 6), (4, 6)]
, Cage 2 Subtract [(4, 1), (5, 1)]
, Cage 6 Multiply [(4, 2), (4, 3), (5, 2)]
, Cage 5 Subtract [(4, 4), (4, 5)]
, Cage 15 Add [(5, 3), (5, 4), (6, 3), (6, 4)]
, Cage 6 Multiply [(5, 5), (5, 6)]
, Cage 15 Multiply [(6, 1), (6, 2)]
, Cage 5 Subtract [(6, 5), (6, 6)]
]
5 4 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
6 1 4 5 3 2
3 5 2 4 6 1
> solveKenKen kk6 [1 .. ]
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Open cells: 36
(1,3) -> [1]
. . 1 . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Queue length: 0
. . 1 . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Open cells: 35
(1,4) -> [3]
. . 1 3 . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Queue length: 0
. . 1 3 . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Open cells: 34
(2,4) -> [1]
. . 1 3 . .
. . . 1 . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Queue length: 0
. . 1 3 . .
. . . 1 . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Open cells: 33
(2,1) -> [2]
. . 1 3 . .
2 . . 1 . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Queue length: 0
. . 1 3 . .
2 . . 1 . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Open cells: 32
(3,1) -> [1]
. . 1 3 . .
2 . . 1 . .
1 . . . . .
. . . . . .
. . . . . .
. . . . . .
Queue length: 0
. . 1 3 . .
2 . . 1 . .
1 . . . . .
. . . . . .
. . . . . .
. . . . . .
Open cells: 31
(4,4) -> [6]
. . 1 3 . .
2 . . 1 . .
1 . . . . .
. . . 6 . .
. . . . . .
. . . . . .
Queue length: 0
. . 1 3 . .
2 . . 1 . .
1 . . . . .
. . . 6 . .
. . . . . .
. . . . . .
Open cells: 30
(4,5) -> [1]
. . 1 3 . .
2 . . 1 . .
1 . . . . .
. . . 6 1 .
. . . . . .
. . . . . .
Queue length: 0
. . 1 3 . .
2 . . 1 . .
1 . . . . .
. . . 6 1 .
. . . . . .
. . . . . .
Open cells: 29
(6,5) -> [6]
. . 1 3 . .
2 . . 1 . .
1 . . . . .
. . . 6 1 .
. . . . . .
. . . . 6 .
Queue length: 0
. . 1 3 . .
2 . . 1 . .
1 . . . . .
. . . 6 1 .
. . . . . .
. . . . 6 .
Open cells: 28
(1,5) -> [2]
. . 1 3 2 .
2 . . 1 . .
1 . . . . .
. . . 6 1 .
. . . . . .
. . . . 6 .
Queue length: 0
. . 1 3 2 .
2 . . 1 . .
1 . . . . .
. . . 6 1 .
. . . . . .
. . . . 6 .
Open cells: 27
(1,6) -> [6]
. . 1 3 2 6
2 . . 1 . .
1 . . . . .
. . . 6 1 .
. . . . . .
. . . . 6 .
Queue length: 0
. . 1 3 2 6
2 . . 1 . .
1 . . . . .
. . . 6 1 .
. . . . . .
. . . . 6 .
Open cells: 26
(5,5) -> [3]
. . 1 3 2 6
2 . . 1 . .
1 . . . . .
. . . 6 1 .
. . . . 3 .
. . . . 6 .
Queue length: 0
. . 1 3 2 6
2 . . 1 . .
1 . . . . .
. . . 6 1 .
. . . . 3 .
. . . . 6 .
Open cells: 25
(3,5) -> [4]
. . 1 3 2 6
2 . . 1 . .
1 . . . 4 .
. . . 6 1 .
. . . . 3 .
. . . . 6 .
Queue length: 0
. . 1 3 2 6
2 . . 1 . .
1 . . . 4 .
. . . 6 1 .
. . . . 3 .
. . . . 6 .
Open cells: 24
(2,5) -> [5]
. . 1 3 2 6
2 . . 1 5 .
1 . . . 4 .
. . . 6 1 .
. . . . 3 .
. . . . 6 .
Queue length: 0
. . 1 3 2 6
2 . . 1 5 .
1 . . . 4 .
. . . 6 1 .
. . . . 3 .
. . . . 6 .
Open cells: 23
(3,4) -> [2]
. . 1 3 2 6
2 . . 1 5 .
1 . . 2 4 .
. . . 6 1 .
. . . . 3 .
. . . . 6 .
Queue length: 0
. . 1 3 2 6
2 . . 1 5 .
1 . . 2 4 .
. . . 6 1 .
. . . . 3 .
. . . . 6 .
Open cells: 22
(6,6) -> [1]
. . 1 3 2 6
2 . . 1 5 .
1 . . 2 4 .
. . . 6 1 .
. . . . 3 .
. . . . 6 1
Queue length: 0
. . 1 3 2 6
2 . . 1 5 .
1 . . 2 4 .
. . . 6 1 .
. . . . 3 .
. . . . 6 1
Open cells: 21
(5,6) -> [2]
. . 1 3 2 6
2 . . 1 5 .
1 . . 2 4 .
. . . 6 1 .
. . . . 3 2
. . . . 6 1
Queue length: 0
. . 1 3 2 6
2 . . 1 5 .
1 . . 2 4 .
. . . 6 1 .
. . . . 3 2
. . . . 6 1
Open cells: 20
(6,4) -> [4]
. . 1 3 2 6
2 . . 1 5 .
1 . . 2 4 .
. . . 6 1 .
. . . . 3 2
. . . 4 6 1
Queue length: 0
. . 1 3 2 6
2 . . 1 5 .
1 . . 2 4 .
. . . 6 1 .
. . . . 3 2
. . . 4 6 1
Open cells: 19
(5,4) -> [5]
. . 1 3 2 6
2 . . 1 5 .
1 . . 2 4 .
. . . 6 1 .
. . . 5 3 2
. . . 4 6 1
Queue length: 0
. . 1 3 2 6
2 . . 1 5 .
1 . . 2 4 .
. . . 6 1 .
. . . 5 3 2
. . . 4 6 1
Open cells: 18
(6,3) -> [2]
. . 1 3 2 6
2 . . 1 5 .
1 . . 2 4 .
. . . 6 1 .
. . . 5 3 2
. . 2 4 6 1
Queue length: 0
. . 1 3 2 6
2 . . 1 5 .
1 . . 2 4 .
. . . 6 1 .
. . . 5 3 2
. . 2 4 6 1
Open cells: 17
(4,3) -> [3]
. . 1 3 2 6
2 . . 1 5 .
1 . . 2 4 .
. . 3 6 1 .
. . . 5 3 2
. . 2 4 6 1
Queue length: 0
. . 1 3 2 6
2 . . 1 5 .
1 . . 2 4 .
. . 3 6 1 .
. . . 5 3 2
. . 2 4 6 1
Open cells: 16
(2,3) -> [6]
. . 1 3 2 6
2 . 6 1 5 .
1 . . 2 4 .
. . 3 6 1 .
. . . 5 3 2
. . 2 4 6 1
Queue length: 0
. . 1 3 2 6
2 . 6 1 5 .
1 . . 2 4 .
. . 3 6 1 .
. . . 5 3 2
. . 2 4 6 1
Open cells: 15
(2,2) -> [3]
. . 1 3 2 6
2 3 6 1 5 .
1 . . 2 4 .
. . 3 6 1 .
. . . 5 3 2
. . 2 4 6 1
Queue length: 0
. . 1 3 2 6
2 3 6 1 5 .
1 . . 2 4 .
. . 3 6 1 .
. . . 5 3 2
. . 2 4 6 1
Open cells: 14
(2,6) -> [4]
. . 1 3 2 6
2 3 6 1 5 4
1 . . 2 4 .
. . 3 6 1 .
. . . 5 3 2
. . 2 4 6 1
Queue length: 0
. . 1 3 2 6
2 3 6 1 5 4
1 . . 2 4 .
. . 3 6 1 .
. . . 5 3 2
. . 2 4 6 1
Open cells: 13
(3,3) -> [5]
. . 1 3 2 6
2 3 6 1 5 4
1 . 5 2 4 .
. . 3 6 1 .
. . . 5 3 2
. . 2 4 6 1
Queue length: 0
. . 1 3 2 6
2 3 6 1 5 4
1 . 5 2 4 .
. . 3 6 1 .
. . . 5 3 2
. . 2 4 6 1
Open cells: 12
(3,2) -> [6]
. . 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 .
. . 3 6 1 .
. . . 5 3 2
. . 2 4 6 1
Queue length: 0
. . 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 .
. . 3 6 1 .
. . . 5 3 2
. . 2 4 6 1
Open cells: 11
(3,6) -> [3]
. . 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
. . 3 6 1 .
. . . 5 3 2
. . 2 4 6 1
Queue length: 0
. . 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
. . 3 6 1 .
. . . 5 3 2
. . 2 4 6 1
Open cells: 10
(4,2) -> [2]
. . 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
. 2 3 6 1 .
. . . 5 3 2
. . 2 4 6 1
Queue length: 0
. . 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
. 2 3 6 1 .
. . . 5 3 2
. . 2 4 6 1
Open cells: 9
(4,6) -> [5]
. . 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
. 2 3 6 1 5
. . . 5 3 2
. . 2 4 6 1
Queue length: 0
. . 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
. 2 3 6 1 5
. . . 5 3 2
. . 2 4 6 1
Open cells: 8
(4,1) -> [4]
. . 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
. . . 5 3 2
. . 2 4 6 1
Queue length: 0
. . 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
. . . 5 3 2
. . 2 4 6 1
Open cells: 7
(1,1) -> [5]
5 . 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
. . . 5 3 2
. . 2 4 6 1
Queue length: 0
5 . 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
. . . 5 3 2
. . 2 4 6 1
Open cells: 6
(1,2) -> [4]
5 4 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
. . . 5 3 2
. . 2 4 6 1
Queue length: 0
5 4 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
. . . 5 3 2
. . 2 4 6 1
Open cells: 5
(5,1) -> [6]
5 4 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
6 . . 5 3 2
. . 2 4 6 1
Queue length: 0
5 4 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
6 . . 5 3 2
. . 2 4 6 1
Open cells: 4
(5,2) -> [1]
5 4 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
6 1 . 5 3 2
. . 2 4 6 1
Queue length: 0
5 4 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
6 1 . 5 3 2
. . 2 4 6 1
Open cells: 3
(5,3) -> [4]
5 4 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
6 1 4 5 3 2
. . 2 4 6 1
Queue length: 0
5 4 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
6 1 4 5 3 2
. . 2 4 6 1
Open cells: 2
(6,1) -> [3]
5 4 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
6 1 4 5 3 2
3 . 2 4 6 1
Queue length: 0
5 4 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
6 1 4 5 3 2
3 . 2 4 6 1
Open cells: 1
(6,2) -> [5]
5 4 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
6 1 4 5 3 2
3 5 2 4 6 1
Queue length: 0
5 4 1 3 2 6
2 3 6 1 5 4
1 6 5 2 4 3
4 2 3 6 1 5
6 1 4 5 3 2
3 5 2 4 6 1
An 8x8 example
kk8 = [ Cage 14 Multiply [(1, 1), (1, 2), (1, 3)]
, Cage 56 Multiply [(1, 4), (2, 3), (2, 4)]
, Cage 7 Subtract [(1, 5), (2, 5)]
, Cage 1 Subtract [(1, 6), (1, 7)]
, Cage 2 Divide [(1, 8), (2, 8)]
, Cage 4 Subtract [(2, 1), (3, 1)]
, Cage 3 Subtract [(2, 2), (3, 2)]
, Cage 18 Add [(2, 6), (3, 6), (4, 6)]
, Cage 9 Add [(2, 7), (3, 7), (3, 8)]
, Cage 6 Add [(3, 3), (4, 3)]
, Cage 60 Multiply [(3, 4), (3, 5), (4, 4)]
, Cage 2 Subtract [(4, 1), (5, 1)]
, Cage 3 Add [(4, 2), (5, 2)]
, Cage 3 Divide [(4, 5), (5, 5)]
, Cage 6 Subtract [(4, 7), (5, 7)]
, Cage 40 Multiply [(4, 8), (5, 8)]
, Cage 2 Divide [(5, 3), (6, 3)]
, Cage 20 Add [(5, 4), (6, 4), (6, 5)]
, Cage 6 Add [(5, 6), (6, 6), (7, 6)]
, Cage 3 Subtract [(6, 1), (7, 1)]
, Cage 13 Add [(6, 2), (7, 2), (7, 3)]
, Cage 17 Add [(6, 7), (6, 8), (7, 7)]
, Cage 7 Subtract [(7, 4), (8, 4)]
, Cage 2 Subtract [(7, 5), (8, 5)]
, Cage 6 Subtract [(7, 8), (8, 8)]
, Cage 13 Add [(8,1), (8, 2), (8, 3)]
, Cage 5 Subtract [(8,6), (8, 7)]
]
1 7 2 4 8 5 6 3
3 5 7 2 1 8 4 6
7 8 1 5 4 6 3 2
6 1 5 3 2 4 7 8
8 2 4 7 6 3 1 5
2 3 8 6 7 1 5 4
5 4 6 1 3 2 8 7
4 6 3 8 5 7 2 1
> solveKenKen kk8 [1, 2, 3, 10, 20, 30, 40, 50, 60]
_ _ _ _ 8 _ _ _
_ _ _ _ 1 _ _ _
_ _ _ _ _ _ _ _
_ _ _ _ 2 _ _ _
_ _ _ _ 6 _ _ _
_ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _
Open cells: 60
(7,5) -> [3,5,7]
_ _ _ _ 8 _ _ _
_ _ _ _ 1 _ _ _
_ _ _ _ _ _ _ _
_ _ _ _ 2 _ _ _
_ _ _ _ 6 _ _ _
_ _ _ _ _ _ _ _
_ _ _ _ 3 _ _ _
_ _ _ _ _ _ _ _
Queue length: 3
_ 7 _ _ 8 _ _ _
_ 6 _ _ 1 _ _ _
_ 3 _ _ 4 _ _ _
_ 1 _ _ 2 _ _ _
_ 2 _ _ 6 _ _ _
_ _ _ _ 7 _ _ _
_ _ _ _ 3 _ _ _
_ 8 _ _ 5 _ _ _
Open cells: 50
(6,2) -> [4,5]
_ 7 _ _ 8 _ _ _
_ 6 _ _ 1 _ _ _
_ 3 _ _ 4 _ _ _
_ 1 _ _ 2 _ _ _
_ 2 _ _ 6 _ _ _
_ 4 _ _ 7 _ _ _
_ _ _ _ 3 _ _ _
_ 8 _ _ 5 _ _ _
Queue length: 7
_ 7 _ 4 8 _ _ _
_ 6 _ 2 1 _ _ _
_ 3 _ 5 4 _ _ _
_ 1 _ 3 2 _ _ _
_ 2 _ 7 6 _ _ _
_ 4 _ 6 7 _ _ _
_ 5 _ 8 3 _ _ _
_ 8 _ 1 5 _ _ _
Open cells: 40
(2,3) -> [7]
_ 7 _ 4 8 _ _ _
_ 6 7 2 1 _ _ _
_ 3 _ 5 4 _ _ _
_ 1 _ 3 2 _ _ _
_ 2 _ 7 6 _ _ _
_ 4 _ 6 7 _ _ _
_ 5 _ 8 3 _ _ _
_ 8 _ 1 5 _ _ _
Queue length: 8
_ 7 _ _ 8 _ _ _
_ 8 _ _ 1 _ _ _
_ 5 _ _ 4 _ _ _
_ 1 _ _ 2 _ _ _
_ 2 _ _ 6 _ _ _
_ _ _ _ 7 _ _ _
_ 4 _ _ 3 _ _ _
_ _ _ _ 5 _ _ _
Open cells: 50
(6,2) -> [3]
_ 7 _ _ 8 _ _ _
_ 8 _ _ 1 _ _ _
_ 5 _ _ 4 _ _ _
_ 1 _ _ 2 _ _ _
_ 2 _ _ 6 _ _ _
_ 3 _ _ 7 _ _ _
_ 4 _ _ 3 _ _ _
_ _ _ _ 5 _ _ _
Queue length: 6
_ 7 _ 4 8 _ _ _
_ 8 _ 2 1 _ _ _
_ 5 _ 3 4 _ _ _
_ 1 _ 5 2 _ _ _
_ 2 _ 7 6 _ _ _
_ 3 _ 6 7 _ _ _
_ 4 _ 8 3 _ _ _
_ 6 _ 1 5 _ _ _
Open cells: 40
(2,3) -> [7]
_ 7 _ 4 8 _ _ _
_ 8 7 2 1 _ _ _
_ 5 _ 3 4 _ _ _
_ 1 _ 5 2 _ _ _
_ 2 _ 7 6 _ _ _
_ 3 _ 6 7 _ _ _
_ 4 _ 8 3 _ _ _
_ 6 _ 1 5 _ _ _
Queue length: 8
_ 7 _ 4 8 _ _ _
_ 8 _ 2 1 _ _ _
_ 5 _ 3 4 _ _ _
_ 1 _ 5 2 _ _ _
_ 2 _ 7 6 _ _ _
_ 3 _ 6 7 _ _ _
_ 4 _ 1 3 _ _ _
_ 6 _ 8 5 _ _ _
Open cells: 40
(2,3) -> [7]
_ 7 _ 4 8 _ _ _
_ 8 7 2 1 _ _ _
_ 5 _ 3 4 _ _ _
_ 1 _ 5 2 _ _ _
_ 2 _ 7 6 _ _ _
_ 3 _ 6 7 _ _ _
_ 4 _ 1 3 _ _ _
_ 6 _ 8 5 _ _ _
Queue length: 7
_ 7 _ _ 8 _ _ _
_ 8 _ _ 1 _ _ _
_ 5 _ _ 4 _ _ _
_ 1 _ _ 2 _ _ _
_ 2 _ _ 6 _ _ _
_ _ _ _ 7 _ _ _
_ 6 _ _ 3 _ _ _
_ _ _ _ 5 _ _ _
Open cells: 50
(6,2) -> [3]
_ 7 _ _ 8 _ _ _
_ 8 _ _ 1 _ _ _
_ 5 _ _ 4 _ _ _
_ 1 _ _ 2 _ _ _
_ 2 _ _ 6 _ _ _
_ 3 _ _ 7 _ _ _
_ 6 _ _ 3 _ _ _
_ _ _ _ 5 _ _ _
Queue length: 5
_ 7 _ 4 8 _ _ _
_ 8 _ 2 1 _ _ _
_ 5 _ 3 4 _ _ _
_ 1 _ 5 2 _ _ _
_ 2 _ 7 6 _ _ _
_ 3 _ 6 7 _ _ _
_ 6 _ 1 3 _ _ _
_ 4 _ 8 5 _ _ _
Open cells: 40
(2,3) -> [7]
_ 7 _ 4 8 _ _ _
_ 8 7 2 1 _ _ _
_ 5 _ 3 4 _ _ _
_ 1 _ 5 2 _ _ _
_ 2 _ 7 6 _ _ _
_ 3 _ 6 7 _ _ _
_ 6 _ 1 3 _ _ _
_ 4 _ 8 5 _ _ _
Queue length: 7
_ 7 _ 4 8 _ _ _
_ 8 _ 2 1 _ _ _
_ 5 _ 3 4 _ _ _
_ 1 _ 5 2 _ _ _
_ 2 _ 7 6 _ _ _
_ 3 _ 6 7 _ _ _
_ 6 _ 8 3 _ _ _
_ 4 _ 1 5 _ _ _
Open cells: 40
(2,3) -> [7]
_ 7 _ 4 8 _ _ _
_ 8 7 2 1 _ _ _
_ 5 _ 3 4 _ _ _
_ 1 _ 5 2 _ _ _
_ 2 _ 7 6 _ _ _
_ 3 _ 6 7 _ _ _
_ 6 _ 8 3 _ _ _
_ 4 _ 1 5 _ _ _
Queue length: 6
_ 7 _ _ 8 _ _ _
_ _ _ _ 1 _ _ _
_ 6 _ _ 4 _ _ _
_ 1 _ _ 2 _ _ _
_ 2 _ _ 6 _ _ _
_ _ _ _ 7 _ _ _
_ 4 _ _ 3 _ _ _
_ 8 _ _ 5 _ _ _
Open cells: 50
(2,2) -> []
Dead end
_ 7 _ _ 8 _ _ _
_ 3 _ _ 1 _ _ _
_ 6 _ _ 4 _ _ _
_ 1 _ _ 2 _ _ _
_ 2 _ _ 6 _ _ _
_ _ _ _ 7 _ _ _
_ 5 _ _ 3 _ _ _
_ _ _ _ 5 _ _ _
Open cells: 50
(6,2) -> [4]
_ 7 _ _ 8 _ _ _
_ 3 _ _ 1 _ _ _
_ 6 _ _ 4 _ _ _
_ 1 _ _ 2 _ _ _
_ 2 _ _ 6 _ _ _
_ 4 _ _ 7 _ _ _
_ 5 _ _ 3 _ _ _
_ _ _ _ 5 _ _ _
Queue length: 5
_ 7 _ _ 8 _ 4 _
_ 3 _ _ 1 _ 5 _
_ 6 _ _ 4 _ 3 _
_ 1 _ _ 2 _ 7 _
_ 2 _ _ 6 _ 1 _
_ 4 _ _ 7 _ 8 _
_ 5 _ _ 3 _ 6 _
_ 8 _ _ 5 _ 2 _
Open cells: 40
(3,4) -> [5]
_ 7 _ _ 8 _ 4 _
_ 3 _ _ 1 _ 5 _
_ 6 _ 5 4 _ 3 _
_ 1 _ _ 2 _ 7 _
_ 2 _ _ 6 _ 1 _
_ 4 _ _ 7 _ 8 _
_ 5 _ _ 3 _ 6 _
_ 8 _ _ 5 _ 2 _
Queue length: 8
_ 7 _ _ 8 _ 5 _
_ 3 _ _ 1 _ 4 _
_ 6 _ _ 4 _ 3 _
_ 1 _ _ 2 _ 7 _
_ 2 _ _ 6 _ 1 _
_ 4 _ _ 7 _ 8 _
_ 5 _ _ 3 _ 6 _
_ 8 _ _ 5 _ 2 _
Open cells: 40
(3,4) -> [5]
_ 7 _ _ 8 _ 5 _
_ 3 _ _ 1 _ 4 _
_ 6 _ 5 4 _ 3 _
_ 1 _ _ 2 _ 7 _
_ 2 _ _ 6 _ 1 _
_ 4 _ _ 7 _ 8 _
_ 5 _ _ 3 _ 6 _
_ 8 _ _ 5 _ 2 _
Queue length: 7
_ 7 _ _ 8 _ _ _
_ _ _ _ 1 _ _ _
_ 6 _ _ 4 _ _ _
_ 1 _ _ 2 _ _ _
_ 2 _ _ 6 _ _ _
_ _ _ _ 7 _ _ _
_ 8 _ _ 3 _ _ _
_ 4 _ _ 5 _ _ _
Open cells: 50
(2,2) -> []
Dead end
_ 7 _ _ 8 _ _ _
_ _ _ _ 1 _ _ _
_ 8 _ _ 4 _ _ _
_ 1 _ _ 2 _ _ _
_ 2 _ _ 6 _ _ _
_ _ _ _ 7 _ _ _
_ 4 _ _ 3 _ _ _
_ 6 _ _ 5 _ _ _
Open cells: 50
(2,2) -> [5]
_ 7 _ _ 8 _ _ _
_ 5 _ _ 1 _ _ _
_ 8 _ _ 4 _ _ _
_ 1 _ _ 2 _ _ _
_ 2 _ _ 6 _ _ _
_ _ _ _ 7 _ _ _
_ 4 _ _ 3 _ _ _
_ 6 _ _ 5 _ _ _
Queue length: 4
_ 7 _ _ 8 _ 6 _
_ 5 _ _ 1 _ 4 _
_ 8 _ _ 4 _ 3 _
_ 1 _ _ 2 _ 7 _
_ 2 _ _ 6 _ 1 _
_ 3 _ _ 7 _ 5 _
_ 4 _ _ 3 _ 8 _
_ 6 _ _ 5 _ 2 _
Open cells: 40
(1,6) -> [5]
_ 7 _ _ 8 5 6 _
_ 5 _ _ 1 _ 4 _
_ 8 _ _ 4 _ 3 _
_ 1 _ _ 2 _ 7 _
_ 2 _ _ 6 _ 1 _
_ 3 _ _ 7 _ 5 _
_ 4 _ _ 3 _ 8 _
_ 6 _ _ 5 _ 2 _
Queue length: 8
1 7 2 4 8 5 6 3
3 5 7 2 1 8 4 6
_ 8 _ _ 4 _ 3 _
_ 1 _ _ 2 _ 7 _
_ 2 _ _ 6 _ 1 _
_ 3 _ _ 7 _ 5 _
_ 4 _ _ 3 _ 8 _
_ 6 _ _ 5 _ 2 _
Open cells: 30
(3,3) -> [1]
1 7 2 4 8 5 6 3
3 5 7 2 1 8 4 6
_ 8 1 _ 4 _ 3 _
_ 1 _ _ 2 _ 7 _
_ 2 _ _ 6 _ 1 _
_ 3 _ _ 7 _ 5 _
_ 4 _ _ 3 _ 8 _
_ 6 _ _ 5 _ 2 _
Queue length: 9
1 7 2 4 8 5 6 3
3 5 7 2 1 8 4 6
7 8 1 5 4 6 3 2
_ 1 _ 3 2 4 7 _
_ 2 _ _ 6 _ 1 _
_ 3 8 6 7 _ 5 _
_ 4 6 _ 3 _ 8 _
_ 6 _ _ 5 _ 2 _
Open cells: 20
(4,3) -> [5]
1 7 2 4 8 5 6 3
3 5 7 2 1 8 4 6
7 8 1 5 4 6 3 2
_ 1 5 3 2 4 7 _
_ 2 _ _ 6 _ 1 _
_ 3 8 6 7 _ 5 _
_ 4 6 _ 3 _ 8 _
_ 6 _ _ 5 _ 2 _
Queue length: 9
1 7 2 4 8 5 6 3
3 5 7 2 1 8 4 6
7 8 1 5 4 6 3 2
6 1 5 3 2 4 7 8
8 2 4 7 6 3 1 5
_ 3 8 6 7 _ 5 _
_ 4 6 1 3 _ 8 _
_ 6 3 _ 5 _ 2 _
Open cells: 10
(7,8) -> [7]
1 7 2 4 8 5 6 3
3 5 7 2 1 8 4 6
7 8 1 5 4 6 3 2
6 1 5 3 2 4 7 8
8 2 4 7 6 3 1 5
_ 3 8 6 7 _ 5 _
_ 4 6 1 3 _ 8 7
_ 6 3 _ 5 _ 2 _
Queue length: 9
1 7 2 4 8 5 6 3
3 5 7 2 1 8 4 6
7 8 1 5 4 6 3 2
6 1 5 3 2 4 7 8
8 2 4 7 6 3 1 5
2 3 8 6 7 1 5 4
5 4 6 1 3 2 8 7
4 6 3 _ 5 _ 2 _
Open cells: 3
(8,4) -> [8]
1 7 2 4 8 5 6 3
3 5 7 2 1 8 4 6
7 8 1 5 4 6 3 2
6 1 5 3 2 4 7 8
8 2 4 7 6 3 1 5
2 3 8 6 7 1 5 4
5 4 6 1 3 2 8 7
4 6 3 8 5 _ 2 _
Queue length: 9
1 7 2 4 8 5 6 3
3 5 7 2 1 8 4 6
7 8 1 5 4 6 3 2
6 1 5 3 2 4 7 8
8 2 4 7 6 3 1 5
2 3 8 6 7 1 5 4
5 4 6 1 3 2 8 7
4 6 3 8 5 _ 2 _
Open cells: 2
(8,6) -> [7]
1 7 2 4 8 5 6 3
3 5 7 2 1 8 4 6
7 8 1 5 4 6 3 2
6 1 5 3 2 4 7 8
8 2 4 7 6 3 1 5
2 3 8 6 7 1 5 4
5 4 6 1 3 2 8 7
4 6 3 8 5 7 2 _
Queue length: 9
1 7 2 4 8 5 6 3
3 5 7 2 1 8 4 6
7 8 1 5 4 6 3 2
6 1 5 3 2 4 7 8
8 2 4 7 6 3 1 5
2 3 8 6 7 1 5 4
5 4 6 1 3 2 8 7
4 6 3 8 5 7 2 _
Open cells: 1
(8,8) -> [1]
1 7 2 4 8 5 6 3
3 5 7 2 1 8 4 6
7 8 1 5 4 6 3 2
6 1 5 3 2 4 7 8
8 2 4 7 6 3 1 5
2 3 8 6 7 1 5 4
5 4 6 1 3 2 8 7
4 6 3 8 5 7 2 1
Queue length: 9
1 7 2 4 8 5 6 3
3 5 7 2 1 8 4 6
7 8 1 5 4 6 3 2
6 1 5 3 2 4 7 8
8 2 4 7 6 3 1 5
2 3 8 6 7 1 5 4
5 4 6 1 3 2 8 7
4 6 3 8 5 7 2 1