Algorithms

31-Dec-11 4:02

This article: Graphical solution to eight queen problem[^] mentions "the old algorithm from Horowitz-Sahani". Does anyone here have more information on this? I haven't found anything online, I'm thinking it's only in a text book.

DaveAuld31-Dec-11 4:49

DaveAuld

31-Dec-11 4:49

This page makes reference to it and it is from a book;
http://penguin.ewu.edu/~trolfe/SCCS-95/SCCS-95.html[^]

This article makes reference to it, and again same book;
http://drdobbs.com/architecture-and-design/184406068[^]

Dave
Find Me On: Web|Facebook|Twitter|LinkedIn

Folding Stats: Team CodeProject

PIEBALDconsult31-Dec-11 15:08

31-Dec-11 15:08

Ah, good, thanks. That first one still just shows the snippet* posted in the article I mentioned, I was hoping to see more on the algorithm.

* And that's what I came up with on my own last week.

Also, I note in the second one that he's using recursion -- my algorithm is non-recursive.

P.S. I just ordered a used copy of that book from Amazon. Thumbs Up | :thumbsup:

modified 1-Jan-12 10:27am.

Member 41945931-Jan-12 13:20

1-Jan-12 13:20

I would be interested in seeing your algo to see how it stacks up with some of my algos for removing recursion.

Dave.

PIEBALDconsult1-Jan-12 16:14

1-Jan-12 16:14

Once I've seen what's in the book I'll decide whether or not mine is unique enough to form an article.

PIEBALDconsult9-Jan-12 13:15

9-Jan-12 13:15

The book arrove today. My code is very much like the code they show on page 338 with two main differences:

0) They have the test in a separate function and therefore a global array.
(Which also has a needless call to ABS.)

1) They have an extra while loop.

public static System.Collections.Generic.IEnumerable<System.Collections.Generic.IList<int>>
nQueens
(
  int HowMany
)
{
  int[] board = new int [ HowMany ] ;
  int   row   = 0 ;

  board [ row ] = -1 ;

  while ( row >= 0 )
  {
    board [ row ]++ ;

    if ( board [ row ] == HowMany )
    {
      row-- ;
    }
    else
    {
      int i ;

      for ( i = 0 ; i < row ; i++ )
      {
        int diff = board [ row ] - board [ i ] ;

        if ( ( diff == 0 ) || ( System.Math.Abs ( diff ) == ( row - i ) ) )
        {
          break ;
        }
      }

      if ( i == row )
      {
        row++ ;

        if ( row == HowMany )
        {
          yield return ( System.Array.AsReadOnly ( board ) ) ;

          row-- ;
        }
        else
        {
          board [ row ] = -1 ;
        }
      }
    }
  }

  yield break ;
}

Member 419459311-Jan-12 8:25

11-Jan-12 8:25

Thank you for your reply. I gather that this is your algorithms since it only has one "while" loop. It may take me a while to digest this, I am primarily a MASM developer, but come here for algorithms.

Do you have any guesses as to how large "HowMany" can be and not run out of memory, i.e., what would be the maximum n for nQueens with this algo?

Dave. (Another Desert Rat from West Phoenix)

PIEBALDconsult11-Jan-12 9:35

11-Jan-12 9:35

Oh, yes, that's mine. The book uses a Pascal-like language the authors created called SPARKS.

On my system (Win 7 32bit, 4GB RAM), somewhere around 438330000 depending on what else is going on:

C:\Projects>nQueens 438330000
^C
C:\Projects>nQueens 438335000
System.OutOfMemoryException: Exception of type 'System.OutOfMemoryException' was thrown.
   at PIEBALD.Lib.LibMth.<nQueens>d__0.MoveNext()
   at PIEBALD.Utilities.nQueens.Main(String[] args)

I have heard that .net limits the size of a structure (e.g. an array) to two gigabytes.

Member 4194593 wrote:
Desert Rat from West Phoenix

Ah, then I invite you to join the Tosche Station group. http://www.codeproject.com/Members/Tosche-Station[^]

modified 11-Jan-12 16:22pm.

Member 419459311-Jan-12 10:01

11-Jan-12 10:01

Does .net limit you if the /3GB switch is used in c:\boot.ini.bat?

Dave.

PIEBALDconsult11-Jan-12 10:22

11-Jan-12 10:22

I expect so, but I haven't tried it.

Member 419459311-Jan-12 10:42

11-Jan-12 10:42

If you go to try it, be aware if the pitfalls:

Boot.ini is System,Hidden,Readonly.

I think you need to be Administrator.

Change the permissions to R/W.

Even as Admin you cannot edit boot.ini with ordinary editors, use RUN NOTEPAD.

Open boot.ini

Change [OS] multi(0)... and add /3GB.

Save boot.ini

For your own safety, change permissions back to RO.

Boot the system.

Also, you do have a good disk image backup don't you?

Dave.

PIEBALDconsult11-Jan-12 11:16

Turing Machine Simulator witch greedy algorithm

11-Jan-12 11:16

Ah, thanks, but I'm not going to try it.

nasser moradbeiki27-Dec-11 2:59

nasser moradbeiki

27-Dec-11 2:59

Turing Machine Simulator
Write a program that simulates a Turing machine (Tm). A Tm is a primitive model of a general purpose computer. Programs for a Tm consist of a collection of quadruples, each of the following form:

<state> <symbol> <action> <nextstate>

where

<state> ::= a non-negative integer
<symbol> ::= 1 | B
<action> ::= <symbol> | L | R
<nextstate> ::= a non-negative integer

A Tm stores data on a tape divided into squares, each of which contains one symbol, either 1 or B. Only one square can be inspected at a time. Initially, a sequence of symbols is written on the tape (this is the input to the Tm), the Tm's "read/write head" is positioned over the leftmost symbol, and the state of the Tm is set to some "start state".

At any point in a Tm computation, the Tm is in a particular state with its read/write head scanning the symbol in a particular square. What happens next depends on whether the Tm's program contains a quadruple whose <state> is the Tm's current state and whose <symbol> is the symbol contained in the square currently being scanned. If such a quadruple exists (there cannot be more than one such), the <action> part of this quadruple controls what happens next:

if <action> specifies a symbol, then that symbol replaces whatever symbol is in the square currently under scan
if <action> is L, the Tm's read/write head is moved one square to the left (the symbol in the square previously under scan is not changed)
if <action> is R, the Tm's read/write head is moved one square to the right (the symbol in the square previously under scan is not changed)
After one of the above actions is done, the Tm changes to state <nextstate> and we repeat the process of searching for an appropriate quadruple to "execute". This is continued until no quadruple matches the current state and symbol under scan, in which case the Tm halts and we consider its output to be the sequence of symbols between the first and last 1's on the tape, inclusive (if no 1's remain, we consider the output to be just B).

The input is a sequence of Tm instruction quadruples followed by a "start" line that specifies the initial state for the Tm, followed by the sequence of symbols that make up the initial value stored on the Tm's tape. Generically:

<state> <symbol> <action> <nextstate>
<state> <symbol> <action> <nextstate>
<state> <symbol> <action> <nextstate>
<state> <symbol> <action> <nextstate>
...
start <state>
<symbol>
<symbol>
<symbol>
<symbol>
<symbol>
...

For example:

0 1 R 0
0 B 1 1
start 0
1
1
1
1

Given the above input, the output should be:

11111

Note
If a quadruple requires moving left from the leftmost symbol on the tape, or right from the rightmost symbol, a square containing the symbol B must be added to the appropriate end of the tape (which is thus "finite, but unbounded")

Re: Turing Machine Simulator witch greedy algorithm

Richard MacCutchan27-Dec-11 4:49

Richard MacCutchan

27-Dec-11 4:49

Nobody is going to write your homework for you.

Unrequited desire is character building. OriginalGriff
I'm sitting here giving you a standing ovation - Len Goodman

Re: Turing Machine Simulator witch greedy algorithm

PIEBALDconsult30-Dec-11 8:33