3 ms·

I am very interested in finding out Emily's approach on this.

by atmosx 13y ago

Jtsummers 13y ago
How I'd approach it by hand, demonstrated on a 4x4 grid (other than 1x1, smallest grid with a solution). I'll go column by column, noting symmetry that also means I only need to check half the rows for the first queen, and with symmetry and the squares she eliminates I'll have fewer options to consider on each subsequent column. +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | | | +---+---+---+---+ | | | X | | +---+---+---+---+ | | | | X | +---+---+---+---+ First queen placed, add the second we only have two options so I'll try the top one. +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | X | | +---+---+---+---+ | | Q | X | X | +---+---+---+---+ | | | X | X | +---+---+---+---+ Oops, gotta move the second queen: +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | Q | X | +---+---+---+---+ | | | X | X | +---+---+---+---+ | | Q | X | X | +---+---+---+---+ Uh oh, can't place the 4th. Moving the first queen since we've exhausted all placements of the 3rd and 2nd queen with the 1st in the upper corner. +---+---+---+---+ | | X | | | +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | | | +---+---+---+---+ | | | X | | +---+---+---+---+ +---+---+---+---+ | | X | Q | X | +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | X | Q | +---+---+---+---+ | | Q | X | X | +---+---+---+---+ I placed the remainder at once because there was only one legal placement in each column. Extending this approach to 8x8 isn't difficult if the challenge is merely to find a solution. EDIT: I found it in 3 attempts on the 8x8. Going to the column with the most constraints (fewest options) to minimize my branching.
- Crito 13y ago
  How I'd do it by hand: Each row must have a queen, and each row must have the queen in a different position. Therefore there are 8 rows and we just need to find a correct permutation of them. Number each row 0 through 7. Generate permutations of these numbers. To check for diagonal collisions between permutation indices x and y: abs(perm[x]-perm[y]) == abs(x-y) (In other words, if rows 2 and 4 cannot be two places apart, rows 6 and 7 cannot be one place apart.) Check for diagonal collisions as you're writing out possible valid permutations by hand. Doesn't take long to generate solutions since you don't have to actually draw or mentally picture a board to work out diagonal collisions. You just need to keep 8 single digit numbers in your head.

I am very interested in finding out Emily's approach on this.

by atmosx 13y ago

I am very interested in finding out Emily's approach on this.

How I'd approach it by hand, demonstrated on a 4x4 grid (other than 1x1, smallest grid with a solution). I'll go column by column, noting symmetry that also means I only need to check half the rows for the first queen, and with symmetry and the squares she eliminates I'll have fewer options to consider on each subsequent column. +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | | | +---+---+---+---+ | | | X | | +---+---+---+---+ | | | | X | +---+---+---+---+ First queen placed, add the second we only have two options so I'll try the top one. +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | X | | +---+---+---+---+ | | Q | X | X | +---+---+---+---+ | | | X | X | +---+---+---+---+ Oops, gotta move the second queen: +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | Q | X | +---+---+---+---+ | | | X | X | +---+---+---+---+ | | Q | X | X | +---+---+---+---+ Uh oh, can't place the 4th. Moving the first queen since we've exhausted all placements of the 3rd and 2nd queen with the 1st in the upper corner. +---+---+---+---+ | | X | | | +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | | | +---+---+---+---+ | | | X | | +---+---+---+---+ +---+---+---+---+ | | X | Q | X | +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | X | Q | +---+---+---+---+ | | Q | X | X | +---+---+---+---+ I placed the remainder at once because there was only one legal placement in each column. Extending this approach to 8x8 isn't difficult if the challenge is merely to find a solution. EDIT: I found it in 3 attempts on the 8x8. Going to the column with the most constraints (fewest options) to minimize my branching.

Crito 13y ago
How I'd do it by hand: Each row must have a queen, and each row must have the queen in a different position. Therefore there are 8 rows and we just need to find a correct permutation of them. Number each row 0 through 7. Generate permutations of these numbers. To check for diagonal collisions between permutation indices x and y: abs(perm[x]-perm[y]) == abs(x-y) (In other words, if rows 2 and 4 cannot be two places apart, rows 6 and 7 cannot be one place apart.) Check for diagonal collisions as you're writing out possible valid permutations by hand. Doesn't take long to generate solutions since you don't have to actually draw or mentally picture a board to work out diagonal collisions. You just need to keep 8 single digit numbers in your head.