当前位置:主页 > 资料 >

Punch cards and BASIC flings, BAck-Tracking, and Eight Queen
栏目分类:资料   发布日期:2018-08-03   浏览次数:

导读:本文为去找网小编(www.7zhao.net)为您推荐的Punch cards and BASIC flings, BAck-Tracking, and Eight Queens: Reg Braithwaites Unexpected...,希望对您有所帮助,谢谢! A few weeks ago, I ordered a 150th anniversary editio

本文为去找网小编(www.7zhao.net)为您推荐的Punch cards and BASIC flings, BAck-Tracking, and Eight Queens: Reg Braithwaite's Unexpected...,希望对您有所帮助,谢谢!

欢迎访问www.7zhao.net



A few weeks ago, I ordered a 150th anniversary edition of . As is their wont, Amazon’s collaborative filters showed me other books that might be of interest to me, and I spotted a copy of :

欢迎访问www.7zhao.net

I nearly gasped out loud, savouring the memory of one of the earliest computer programs that I ever wrote from scratch, a program that searched for solutions to the eight queens puzzle. www.7zhao.net

Prelude: 1972 – 1977

In the nineteen-seventies, I spent a lot of time in Toronto’s libraries. My favourite hangouts were the Sanderson Branch (which was near my home in Little Italy), and the “Spaced Out Library,” a non-circulating collection of science fiction and fantasy that had been donated by and was housed within St. George and College Street branch.

去找(www.7zhao.net欢迎您

I especially enjoyed reading back issues of Scientific American, and like many, I was captivated by “Mathematical Games” columns. My mother had sent me to a day camp for gifted kids once, and it was organized like a university. The “students” self-selected electives, and I picked one called “Whodunnit.” It turned out to be a half-day exercise in puzzles and games, and I was hooked. www.7zhao.net

Where else would I learn about playing tic-tac-toe in a hypercube? Or about liars and truth-tellers? Or, as it happened, about Martin Gardner? I suspect the entire material was lifted from his collections of columns, and that suited me down to the ground. www.7zhao.net

One day we had a field trip to the University of Toronto’s High-Speed Job Stream, located in the Sanford Fleming Building. This was a big room that had a line printer on one side of it, a punch card reader on the other, and lots and lots of stations for punching your own cards.

copyright www.7zhao.net

To run a job, you typed out your program, one line per card, and then stuck a header on the front that told the batch job what kind of interpreter or compiler to use. Those cards were brightly coloured, and had words like orSNOBOL printed on them in huge letters.

本文来自去找www.7zhao.net

You put header plus program into the hopper at the back, waited, and when it emerged from the reader, collected your punch cards and headed over to the large and noisy line printer. When the IBM 360 got around to actually running your job, it would print the results for you, and you would head over to a table to review the output and–nearly all of the time for me–find the typo or bug, update your program, and start all over again.

本文来自去找www.7zhao.net

You can see equipment like this in any computer museum, so I won’t go into much more detail. Besides, the mechanics of running programs as batch jobs was not the interesting thing about the High Speed Job Stream. The interesting thing about the High Speed Job Stream was that there was no restriction on running jobs . You didn’t need an account or a password. Nobody stood at the door asking for proof that you were an undergrad working on an assignment.

内容来自www.7zhao.net

So I’d go over there on a summer day and write software, and sometimes, I’d try to write programs to solve puzzles.

内容来自www.7zhao.net

去找(www.7zhao.net欢迎您

school

In the autumn of 1976, I packed my bags and went to , a boarding school. One of the amazing things about “SAC” was that they had an actual minicomputer on the campus. For the time, this was unprecedented. In Ontario’s public school system, it was possible to take courses in programming, but they nearly all involved writing programs by filling in “bubble cards” with a pencil and submitting jobs overnight.

本文来自去找www.7zhao.net

At SAC, there was a in a room with–oh glorious day–four ancient teletype machines hooked up to it with what I now presume were serial ports. It had various operating modes that were set by loading a 5MB removable hard disk (It was a 12” platter encased in a big protective plastic shell), and rebooting the machine by toggling bootstrap instructions into the front panel. 内容来自www.7zhao.net

The mode set up for student use was a four-user BASIC interpreter. It had 16KB of RAM (yes, you read that right), and its simple model partitioned the memory so that each user got 4KB to themselves. You could type your program into the teletype, and its output would print on a roll of paper. www.7zhao.net

Saving programs on disc was not allowed. The teletypes had paper tape interfaces on the side, so to save a program we would LIST the source with the paper tape on, and it would punch ASCII or EBDIC codes onto the tape. We’d tear it off and take it with us. Later, to reload a program, we’d feed the tape into the teletype and it would act as if we were typing the program anew. 去找(www.7zhao.net欢迎您

4KB was enough for assignments like writing a simple bubble sort, but I had discovered by this time, and programs like “Super Star Trek” did not fit in 4KB. There was a 16KB single-user disc locked in a cabinet alongside programs for tabulating student results. 内容来自www.7zhao.net

In defiance of all regulation, I would go in late, pick the cupboard’s lock, remove the disc I wanted, and boot up single-user mode. I could then work on customizing Super Star Trek or write programs to solve puzzles. Curiously, I never tampered with the student records. I was a morally vacant vessel at that pointy in my life: I’m not going to tell you that I had a moral code about these things. I think the truth is that I just didn’t care about marks. 去找(www.7zhao.net欢迎您

Now about puzzles. One of the things I worked on was writing new games. I made a program that would play the Maharajah while I played the standard chess pieces. It could beat me, which was enough AI for my purposes. This got me thinking about something I’d read in a Martin Gardner book, the . 本文来自去找www.7zhao.net

I decided to write a program to search for the solutions by brute force.

内容来自www.7zhao.net

内容来自www.7zhao.net

The Eight Queens Puzzle

As Wikipedia explains, “The is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.” 内容来自www.7zhao.net

By this time I knew a little about writing “generate and test” algorithms, as well as a little about depth-first search from writing games (like “Maharajah and the Sepoys”) that performed basic searches for moves to make. So I set about writing a BASIC program to search for solutions. I had no real understanding of computational complexity and running time, but what if I wrote a program and left it running all night?

欢迎访问www.7zhao.net

The truly brute force solution looks something like this (BASIC has a for... next construct, but close enough): 本文来自去找www.7zhao.net

outer: for (let i0 = 0; i0 <= 7; ++i0) {
 for (let j0 = 0; j0 <= 7; ++j0) {
   for (let i1 = 0; i1 <= 7; ++i1) {
     for (let j1 = 0; j1 <= 7; ++j1) {
       for (let i2 = 0; i2 <= 7; ++i2) {
         for (let j2 = 0; j2 <= 7; ++j2) {
           for (let i3 = 0; i3 <= 7; ++i3) {
             for (let j3 = 0; j3 <= 7; ++j3) {
               for (let i4 = 0; i4 <= 7; ++i4) {
                 for (let j4 = 0; j4 <= 7; ++j4) {
                   for (let i5 = 0; i5 <= 7; ++i5) {
                     for (let j5 = 0; j5 <= 7; ++j5) {
                       for (let i6 = 0; i6 <= 7; ++i6) {
                         for (let j6 = 0; j6 <= 7; ++j6) {
                           for (let i7 = 0; i7 <= 7; ++i7) {
                             inner: for (let j7 = 0; j7 <= 7; ++j7) {
                               const board = [
                                 [".", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", ".", ".", ".", ".", "."]
                               ];

                               const queens = [
                                 [i0, j0],
                                 [i1, j1],
                                 [i2, j2],
                                 [i3, j3],
                                 [i4, j4],
                                 [i5, j5],
                                 [i6, j6],
                                 [i7, j7]
                               ];

                               for (const [i, j] of queens) {
                                 if (board[i][j] != '.') {
                                   // square is occupied or threatened
                                   continue inner;
                                 }

                                 for (let k = 0; k <= 7; ++k) {
                                   // fill row and column
                                   board[i][k] = board[k][j] = "x";

                                   const vOffset = k-i;
                                   const hDiagonal1 = j - vOffset;
                                   const hDiagonal2 = j + vOffset;

                                   // fill diagonals
                                   if (hDiagonal1 >= 0 && hDiagonal1 <= 7) {
                                     board[k][hDiagonal1] = "x";
                                   }

                                   if (hDiagonal2 >= 0 && hDiagonal2 <= 7) {
                                     board[k][hDiagonal2] = "x";
                                   }
                                 }
                               }

                               const out = [
                                 [".", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", ".", ".", ".", ".", "."],
                                 [".", ".", ".", ".", ".", ".", ".", "."]
                               ];

                               for (const [i, j] of queens) {
                                 out[i][j] = "Q";
                               }

                               console.log(out.map(row => row.join('')).join("\n"));
                               break outer;
                             }
                           }
                         }
                       }
                     }
                   }
                 }
               }
             }
           }
         }
       }
     }
   }
 }
} copyright www.7zhao.net 

I believe I tried that, left the program running overnight, and when I came in the next morning before school it was still running. It was searching 8^16 (or more accurately, 64^8 ) candidates for a solution, that’s 281,474,976,710,656 loops. Given the speed of that minicomputer, I suspect the program would still be running today.

本文来自去找www.7zhao.net

Then I had an insight of sorts: If I could arrange an ordering of queens, then if I set about generating all the possible arrangements for the first queen, by definition the subsequent queens would have to come after each queen’s position. copyright www.7zhao.net

Before writing out the code for this small improvement, I’ll share what happened when I tested my conjecture. www.7zhao.net

copyright www.7zhao.net

disaster strikes

First, I had neglected to insert code to halt the program when it found a solution. Perhaps I wanted to print all of the solutions. Second, I tried to optimize my test subroutine at the same time, and inserted a bug. Or perhaps, the bug was already there, but it didn’t manifest itself until the program was deeper into its search, and my “optimization” took it to the failure case more quickly.

去找(www.7zhao.net欢迎您

In any event, I left the updated program running overnight, and once again returned before breakfast to see if it had found any solutions. When I entered the room, there was a horrible smell and a deafening clacking sound. The test function had failed at some point, and it was passing thousands of positions in rapid order. 本文来自去找www.7zhao.net

The paper roll had jammed at some point in the night and was no longer advancing, but the teletype had hammered through the paper and was hammering on the roller behind. Rolls of paper had emerged from the machine and lay in a heap around it. I consider it a very lucky escape that a spark hadn’t ignited the paper or its dust that hung in the air.

去找(www.7zhao.net欢迎您

I shut everything down, cleaned up as best I could, and then set about finding the bug. 去找(www.7zhao.net欢迎您

本文来自去找www.7zhao.net

separating concerns

The crux of my “insight” is realizing that the number of unique choices of eight distint squares is much smaller than 64^8 . For starters, if we eliminate the cases where two queens are on the same square, we’re already down from 64^8 to 64!/56! ( 64*63*62*61*60*59*58*57 ). That reduces the search space to 178,462,987,637,760 candidates, about half as many as the original pure brute force. 内容来自www.7zhao.net

But we also don’t care about the ordering, so what we want are , not permutations. That reduces our search space again, down to 64!/(8!*56!) , or 4,426,165,368 ways to choose 8 squares from 64. 欢迎访问www.7zhao.net

One of our go-to techniques for modifying programs is to begin my making sure that the thing we wish to change is refactored into its own responsibility, then we can make a change to just one thing. The JavaScript analog of my old BASIC code has the generating loops, function testing code, and output code all higgledy-piggledy.

去找(www.7zhao.net欢迎您

We might begin be refactoring into a generator and consumer. We can then modify the generator as we see fit: 欢迎访问www.7zhao.net

function * bruteForceCombinations () {
  for (let i0 = 0; i0 <= 7; ++i0) {
    for (let j0 = 0; j0 <= 7; ++j0) {
      for (let i1 = 0; i1 <= 7; ++i1) {
        for (let j1 = 0; j1 <= 7; ++j1) {
          for (let i2 = 0; i2 <= 7; ++i2) {
            for (let j2 = 0; j2 <= 7; ++j2) {
              for (let i3 = 0; i3 <= 7; ++i3) {
                for (let j3 = 0; j3 <= 7; ++j3) {
                  for (let i4 = 0; i4 <= 7; ++i4) {
                    for (let j4 = 0; j4 <= 7; ++j4) {
                      for (let i5 = 0; i5 <= 7; ++i5) {
                        for (let j5 = 0; j5 <= 7; ++j5) {
                          for (let i6 = 0; i6 <= 7; ++i6) {
                            for (let j6 = 0; j6 <= 7; ++j6) {
                              for (let i7 = 0; i7 <= 7; ++i7) {
                                for (let j7 = 0; j7 <= 7; ++j7) {
                                  const queens = [
                                    [i0, j0],
                                    [i1, j1],
                                    [i2, j2],
                                    [i3, j3],
                                    [i4, j4],
                                    [i5, j5],
                                    [i6, j6],
                                    [i7, j7]
                                  ];

                                  yield queens;
                                }
                              }
                            }
                          }
                        }
                      }
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}

function test (queens) {
  const board = [
    [".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", "."]
  ];

  for (const [i, j] of queens) {
    if (board[i][j] != '.') {
      // square is occupied or threatened
      return false;
    }

    for (let k = 0; k <= 7; ++k) {
      // fill row and column
      board[i][k] = board[k][j] = "x";

      const vOffset = k-i;
      const hDiagonal1 = j - vOffset;
      const hDiagonal2 = j + vOffset;

      // fill diagonals
      if (hDiagonal1 >= 0 && hDiagonal1 <= 7) {
        board[k][hDiagonal1] = "x";
      }

      if (hDiagonal2 >= 0 && hDiagonal2 <= 7) {
        board[k][hDiagonal2] = "x";
      }

      board[i][j] = "Q";
    }
  }

  return true;
}

function stringify (queens) {
  const board = [
    [".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", "."]
  ];

  for (const [i, j] of queens) {
    board[i][j] = "Q";
  }

  return board.map(row => row.join('')).join("\n");
}

function * filter (predicateFunction, iterable) {
  for (const element of iterable) {
    if (predicateFunction(element)) {
      yield element;
    }
  }
}

function first (iterable) {
  const [value] = iterable;

  return value;
}

const allSolutions = filter(test, bruteForceCombinations());
const firstSolution = first(allSolutions);

stringify(firstSolution) www.7zhao.net 

With this in hand, we can make a faster “combinations” generator, and we won’t have to work around any of the other code.

欢迎访问www.7zhao.net

去找(www.7zhao.net欢迎您

the “combinations” algorithm

An easy way to implement choosing combinations of squares is to work with numbers from 0 to 63 instead of pairs of indices. Here’s a generator that does the exact thing we want: www.7zhao.net

function * map (mapFunction, iterable) {
  for (const element of iterable) {
    yield mapFunction(element);
  }
}

function * choose (n, k, offset = 0) {
  if (k === 1) {
    for (let i = 0; i <= (n - k); ++i) {
      yield [i + offset];
    }
  } else if (k > 1) {
    for (let i = 0; i <= (n - k); ++i) {
      const remaining = n - i - 1;
      const otherChoices = choose(remaining, k - 1, i + offset + 1);

      yield * map(x => [i + offset].concat(x), otherChoices);
    }
  }
}

choose(5, 3)
  //=>
    [0, 1, 2]
    [0, 1, 3]
    [0, 1, 4]
    [0, 2, 3]
    [0, 2, 4]
    [0, 3, 4]
    [1, 2, 3]
    [1, 2, 4]
    [1, 3, 4]
    [2, 3, 4] 本文来自去找www.7zhao.net 

We can now write choose(64, 8) to get all the ways to choose eight squares, and [Math.floor(q/8), q % 8] to convert a number from 0 to 63 into a pair of indices between 0 and 7 :

copyright www.7zhao.net

const chooseCombinations = map(x => x.map(q => [Math.floor(q/8), q % 8]), choose(64, 8));

const allSolutions = filter(test, chooseCombinations);
const firstSolution = first(allSolutions);

stringify(firstSolution) 

欢迎访问www.7zhao.net

It’s still a tremendous number of candidates to search. If we list them out we can see some of the problems right away. For example, the very first combination it wants to test is [[0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7]] . The queens are all on the same row! 内容来自www.7zhao.net

There is an easy fix for this and as a bonus, it gets us solutions really fast. www.7zhao.net

www.7zhao.net

the “rooks” algorithm

We know that eight queens on the same row are not going to work. No two queens can be on the same column or row. So what we really want are all the combinations of eight queens that don’t share a column or row. In other words, every queen will have a unique column and a unique row.

copyright www.7zhao.net

Let’s start with the unique rows. Every time we generate a set of queens, one will be on row 0 , one on row 1 , one on row 2 , and so forth. So since we’re always going to end up with a queen on row 0 , another on row 1 and so Same goes for the columns. To do this, we’ll need to be able to generate the of the numbers from 0 to 7 .

欢迎访问www.7zhao.net

It’s fairly easy to do if we don’t mind splicing and reassembling arrays:

www.7zhao.net

function * permutations (arr, prefix = []) {
  if (arr.length === 1) {
    yield prefix.concat(arr);
  } else if (arr.length > 1) {
    for (let i = 0; i < arr.length; ++i) {
      const chosen = arr[i];
      const remainder = arr.slice(0, i).concat(arr.slice(i+1, arr.length))

      yield * permutations(remainder, prefix.concat([chosen]));
    }
  }
}

permutations([1, 2, 3])
//=> [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] 
欢迎访问www.7zhao.net

And now we can obtain a solution in a split-second:

copyright www.7zhao.net

const queensSharingNoRowsOrColumns = map(
  ii => ii.map((i, j) => [i, j]),
  permutations([0, 1, 2, 3, 4, 5, 6, 7])
);

const allSolutions = filter(test, queensSharingNoRowsOrColumns);
const firstSolution = first(allSolutions);

stringify(firstSolution)

//=>
  Q.......
  ......Q.
  ....Q...
  .......Q
  .Q......
  ...Q....
  .....Q..
  ..Q..... copyright www.7zhao.net 

This is great! We’ve made a huge performance improvement simply by narrowing the “search space.” We’re down to 8! permutations of queens on unique rows and columns, just 40,320 different permutations to try. 欢迎访问www.7zhao.net

(This approach is known as the “rooks” algorithm, because generating the candidate positions for the queens based on permutations of rows and columns is the solution for enumerating all of the ways eight rooks can be placed on a chessboard.)

欢迎访问www.7zhao.net

内容来自www.7zhao.net

faster testing

We’ve certainly sped things up by being smarter about the candidates we submit for testing. But what about the testing itself? The algorithm of filling in squares on a chess board very neatly matches how we might do this mentally, but it is quite slow. How can we make it faster?

本文来自去找www.7zhao.net

For starters, we don’t need to fill in rows and columns by such brute force. We can simplify checking rows and columns with an array representing a row and another representing a column: www.7zhao.net

0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7

Becomes: www.7zhao.net

0 1 2 3 4 5 6 7

And: 内容来自www.7zhao.net

0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6
7 7 7 7 7 7 7 7

Becomes: 欢迎访问www.7zhao.net

0 1 2 3 4 5 6 7

What about diagonals? Observe:

copyright www.7zhao.net

0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 10
4 5 6 7 8 9 10 11
5 6 7 8 9 10 11 12
6 7 8 9 10 11 12 13
7 8 9 10 11 12 13 14

If we sum the row and column number ( row + col ), we get a number representing the position of one of a queen’s diagonals. We can thus use:

内容来自www.7zhao.net

0 1 2 3 4 5 7 7 8 9 10 11 12 13 14

What about the other diagonal? 本文来自去找www.7zhao.net

7 6 5 4 3 2 1 0
8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2
10 9 8 7 6 5 4 3
11 10 9 8 7 6 5 4
12 11 10 9 8 7 6 5
13 12 11 10 9 8 7 6
14 13 12 11 10 9 8 7

Ah! We can sum the row with the inverse of the column number ( row + 7 - col ). We than then use:

本文来自去找www.7zhao.net

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Like this:

去找(www.7zhao.net欢迎您

function fastTest (queens) {
  const ns = [".", ".", ".", ".", ".", ".", ".", "."];
  const ew = [".", ".", ".", ".", ".", ".", ".", "."];
  const nesw = [".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", "."];
  const nwse = [".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", "."];

  if (queens.length < 2) return true;

  for (const [i, j] of queens) {
    if (
      ns[i] !== '.' ||
      ew[j] !== '.' ||
      nwse[i + j] !== '.' ||
      nesw[i + 7 - j] !== '.'
    ) return false;

    ns[i] = 'x';
    ew[j] = 'x';
    nwse[i + j] = 'x';
    nesw[i + 7 - j] = 'x';
  }

  return true;
}

const allSolutions = filter(fastTest, queensSharingNoRowsOrColumns);
const firstSolution = first(allSolutions);

stringify(firstSolution)

//=>
  Q.......
  ......Q.
  ....Q...
  .......Q
  .Q......
  ...Q....
  .....Q..
  ..Q..... 内容来自www.7zhao.net 

Just as we were able to change the generator independently of the test, now we have changed the test independently of the generator. That’s a good thing. And hey, if we only need to test diagonals, we can be even faster :

内容来自www.7zhao.net

function testDiagonals (queens) {
  const nesw = [".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", "."];
  const nwse = [".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", "."];

  if (queens.length < 2) return true;

  for (const [i, j] of queens) {
    if (nwse[i + j] !== '.' || nesw[i + 7 - j] !== '.') return false;

    nwse[i + j] = 'x';
    nesw[i + 7 - j] = 'x';
  }

  return true;
} 

欢迎访问www.7zhao.net

欢迎访问www.7zhao.net

tree searching

As noted, separating generator from test allows us to optimize and improve each of the two parts independently. If we were mindful of such, we could write test for the two independent pieces. This is all very good. 欢迎访问www.7zhao.net

But that being said, not all improvements can be made independently like this. Any organization of code makes some things easier, but others harder. In my original BASIC program way back in 1977, I built the board as I went, and marked the “threatened” squares. But instead of iterating over all the possible queen positions, as I added queens to the board I iterated over all the open positions. 本文来自去找www.7zhao.net

So after placing the first queen in the first open space, my board looked conceptually like this:

去找(www.7zhao.net欢迎您

Qxxxxxxx
xx......
x.x.....
x..x....
x...x...
x....x..
x.....x.
x......x 去找(www.7zhao.net欢迎您 

The next queen I would try would be in the first “open” square, like this: 去找(www.7zhao.net欢迎您

Qxxxxxxx
xxQxxxxx
xxxx....
x.xxx...
x.x.xx..
x.x..xx.
x.x...xx
x.x....x 

www.7zhao.net

I’d continue like this until there were eight queens, or I ran out of empty spaces. If I failed, I’d backtrack and try a different position for the last queen. If I ran out of different positions for the last queen, I’d try a different position for the second-to-last queen, and so on. 欢迎访问www.7zhao.net

I did not know the words for it, but I was performing a depth-first search of a “tree” of positions. I was trying to find a path that was eight queens deep. And I was keeping the board updated to do so. 欢迎访问www.7zhao.net

This method is better than the combinations approach, but not as good as the rooks approach. It’s interesting nevertheless, because it is an “inductive” method that lends itself to recursive thinking. We begin with the solution for zero queens, and empty board. Then we successively search for ways to add one more queen to whatever we already have, backtracking if we run out of available spaces. 内容来自www.7zhao.net

We can actually combine the inductive and rooks approach. This algorithm builds solutions one row at a time, iterating over the open columns, and checking for diagonal attacks. If there are none, it recursively calls itself to add another row. When it reaches eight rows, it yields the solution. It finds all 92 solutions searching just 5,508 positions (Of which eight are the degenerate case of having just one queen on the first row): 内容来自www.7zhao.net

function * inductive (queens = []) {
  if (queens.length === 8) {
    yield queens;
  } else {
    const candidateColumns = [0, 1, 2, 3, 4, 5, 6, 7];
    for (const [row, column] of queens) {
      candidateColumns[column] = undefined;
    }

    for (const candidateColumn of candidateColumns) {
      if (candidateColumn != null) {
        const candidateQueens = queens.concat([[queens.length, candidateColumn]]);

        if (testDiagonals(candidateQueens)) {
          yield * inductive(candidateQueens);
        }
      }
    }
  }
} 欢迎访问www.7zhao.net 

Unlike our true generate-and-test approach, it interleaves partial generation with testing, so it’s not possible to break it into two separate pieces. But it’s considerably smaller, so it’s fine to extract the test and have inductive call testDiagonals , rather than have them both be independent peers.

去找(www.7zhao.net欢迎您

I wish I’d thought of this approach in 1977! 欢迎访问www.7zhao.net

本文来自去找www.7zhao.net

and so to bed

It was a lot of fun to revisit Martin Gardner’s column on the eight queen’s problem, and especially to rewrite these algorithms forty years later. This post doesn’t have a deep insight into program design, and thus there’s not major point to summarize. 本文来自去找www.7zhao.net

Just as there can be recreational mathematics, there can be recreational programming. And that’s a very fine thing to enjoy.

copyright www.7zhao.net

notes

www.7zhao.net


本文原文地址:http://raganwald.com/2018/08/01/eight-queens.html

以上为Punch cards and BASIC flings, BAck-Tracking, and Eight Queens: Reg Braithwaite's Unexpected...文章的全部内容,若您也有好的文章,欢迎与我们分享!

本文来自去找www.7zhao.net

Copyright ©2008-2017去找网版权所有   皖ICP备12002049号-2 皖公网安备 34088102000435号   关于我们|联系我们| 免责声明|友情链接|网站地图|手机版