Precomputed 3 row matching in 3 by 3 grid (Tic-Tac-Toe)

[kevin]

Precomputed 3 row matching in 3 by 3 grid (Tic-Tac-Toe)  

 This code builds a PSUB that can detect all runs of 3 combinations within a 3 by 3 board ,  as you would need for a game such as Tac-Tac-Toe..   Often  this is done by applying a filter (of sorts) where you'd run through each cell, scanning out in all directions.    Which is short and sweat to program, but not very efficient if you need to perform the action a lot of times.

 Since the grid is only 3 by 3 gird, there's only 8 possible unique winning combinations (rows of 3) ,  3 across, 3 down and 2 diagonals. Which you can easily hard code a solution, but this is just a novel way of doing that.  :)

PlayBASIC Code: [Select]

   /*

      -------------------------------------------------------------------------
      -------------------------------------------------------------------------
      Generate pre-computed 3 by 3 (Tic-Tac-Toe) grid matching function/PSUB.
      -------------------------------------------------------------------------
      -------------------------------------------------------------------------
   
         This routine builds pre-computed output code to solve possible runs
        3 within a 3by 3 grid.   The created function expects the grid 
        to be stored in a set of global varibales named
        
          global Board_X1_Y1  :   global Board_X2_Y1 :  global Board_X3_Y1
          global Board_X1_Y2  :   global Board_X2_Y2 :  global Board_X3_Y2
          global Board_X1_Y3  :   global Board_X2_Y3 :  global Board_X3_Y3
          
        
         So before calling created valid function you'd pull your grid array
         into these.  You can do a mod it to use an array, but variables
         have less overhead quicker.
         
        
       (c) copyright 2015 
      ------------------------------------------------------------------------- */
   
   
   #if pbdebug=0
         #abort "Please compile in debug mode (f6 or f7) as the code is output to the debug console "
   #endif
   
   
   // Cells stored in variables
   cr$=chr$(13)+chr$(10)
   tab1$=chr$(9)
   tab2$=make$(chr$(9),2)

   TargetVariable$="Key"

   code$+="Psub Match_3by3_Grid(Key)"+Cr$
   code$+=cr$
   code$+=tab1$+"Result=0"+Cr$
   code$+=cr$
   
   // -------------------------------------------------------------------------
   // -------------------------------------------------------------------------
   // -------------------------------------------------------------------------
   For ylp=1 to 3

      For xlp=1 to 3


            CurrentCell$="Board_X"+str$(xlp)+"_Y"+str$(ylp)

            // Make a divider
            code$+="; "+make$("-",100)+cr$
            code$+="SolveBoardAt_X"+str$(xlp)+"_Y"+str$(ylp)+":"+cr$
            code$+="; "+make$("-",100)+cr$


            ; ignore test from locations that re already covered
            if xlp>1 and ylp>1 then continue


            code$+=tab1$+"if "+CurrentCell$ +Cr$+cr$

            // compare run from left to right across this span          
            if Xlp=1
                  code$+=Tab2$+"; Hori Strip ------------------------------------"+cr$
                  compares$=" if ("
                  for compareXLP=TrimCord(xlp,0) to TrimCord(xlp,2)
                        ThisCell$="Board_X"+str$(CompareXLP)+"_Y"+str$(ylp)
                        compares$+="("+ThisCell$+"=" +TargetVariable$+")+"
                  next
                  compares$=trimright$(compares$,"+")+")=3 "
                  code$+=tab2$+compares$+" then result=1:goto done"
                  code$+=cr$+cr$
            endif

            if Ylp=1
                  code$+=Tab2$+"; Vert Strip ------------------------------------"+cr$
                  compares$=" if ("
                  for compareYLP=TrimCord(ylp,0) to TrimCord(Ylp,2)
                        ThisCell$="Board_X"+str$(XLP)+"_Y"+str$(CompareYlp)
                        compares$+="("+ThisCell$+"=" +TargetVariable$+")+"
                  next
                  compares$=trimright$(compares$,"+")+")=3 "
                  code$+=tab2$+compares$+" then result=1:goto done"
                  code$+=cr$+cr$

            endif
            
            if Ylp=1 and xlp=1
                  code$+=Tab2$+"; diag down Strip ------------------------------------"+cr$
                  compares$=" if ("
                  for compareLP=0 to 2
                        ThisCell$="Board_X"+str$(compareLP+XLP)+"_Y"+str$(compareLP+ylp)
                        compares$+="("+ThisCell$+"=" +TargetVariable$+")+"
                  next
                  compares$=trimright$(compares$,"+")+")=3 "
                  code$+=tab2$+compares$+" then result=1:goto done"
                  code$+=cr$+cr$
            endif
            

            if Ylp=3 and xlp=1
                  code$+=Tab2$+"; diag up Strip ------------------------------------"+cr$
                  compares$=" if ("
                  for compareLP=0 to 2
                        ThisCell$="Board_X"+str$(compareLP+XLP)+"_Y"+str$(ylp-compareLP)
                        compares$+="("+ThisCell$+"=" +TargetVariable$+")+"
                  next
                  compares$=trimright$(compares$,"+")+")=3 "
                  code$+=tab2$+compares$+" then result=1:goto done"
                  code$+=cr$+cr$
            endif


            code$+=Tab1$+"endif"+Cr$
            
            code$+=cr$+cr$

      next
   next

   
            code$+="Done:"+Cr$
   
            code$+="EndPsub Result"+Cr$
            #print code$
   

   print "code created-> see debugger-console"         

   sync
   waitkey
   



Function TrimCord(CurrentPosition,Offset)
      result=currentPosition+Offset
      if Result<1 then Result=1
      if Result>3 then Result=3
EndFUnction Result



Login required to view complete source code

    Here's the resulting code with some test code. 

PlayBASIC Code: [Select]

   explicit

   local Key=2

   // define board
   global Board_X1_Y1=1 :global Board_X2_Y1=0  :global Board_X3_Y1=1
   global Board_X1_Y2=2 :global Board_X2_Y2=2  :global Board_X3_Y2=2
   global Board_X1_Y3=1 :global Board_X2_Y3=1  :global Board_X3_Y3=1

   
   For Key=1 to 3
      print "Winner State :"+str$(Match_3by3_Grid(Key))
   next

   sync
   waitkey
   end
   
   
Psub Match_3by3_Grid(Key)

   Result=0

; ----------------------------------------------------------------------------------------------------
SolveBoardAt_X1_Y1:
; ----------------------------------------------------------------------------------------------------
   if Board_X1_Y1

      ; Hori Strip ------------------------------------
       if ((Board_X1_Y1=Key)+(Board_X2_Y1=Key)+(Board_X3_Y1=Key))=3  then result=1:goto done

      ; Vert Strip ------------------------------------
       if ((Board_X1_Y1=Key)+(Board_X1_Y2=Key)+(Board_X1_Y3=Key))=3  then result=1:goto done

      ; diag down Strip ------------------------------------
       if ((Board_X1_Y1=Key)+(Board_X2_Y2=Key)+(Board_X3_Y3=Key))=3  then result=1:goto done

   endif


; ----------------------------------------------------------------------------------------------------
SolveBoardAt_X2_Y1:
; ----------------------------------------------------------------------------------------------------
   if Board_X2_Y1

      ; Vert Strip ------------------------------------
       if ((Board_X2_Y1=Key)+(Board_X2_Y2=Key)+(Board_X2_Y3=Key))=3  then result=1:goto done

   endif


; ----------------------------------------------------------------------------------------------------
SolveBoardAt_X3_Y1:
; ----------------------------------------------------------------------------------------------------
   if Board_X3_Y1

      ; Vert Strip ------------------------------------
       if ((Board_X3_Y1=Key)+(Board_X3_Y2=Key)+(Board_X3_Y3=Key))=3  then result=1:goto done

   endif


; ----------------------------------------------------------------------------------------------------
SolveBoardAt_X1_Y2:
; ----------------------------------------------------------------------------------------------------
   if Board_X1_Y2

      ; Hori Strip ------------------------------------
       if ((Board_X1_Y2=Key)+(Board_X2_Y2=Key)+(Board_X3_Y2=Key))=3  then result=1:goto done

   endif


; ----------------------------------------------------------------------------------------------------
SolveBoardAt_X2_Y2:
; ----------------------------------------------------------------------------------------------------
; ----------------------------------------------------------------------------------------------------
SolveBoardAt_X3_Y2:
; ----------------------------------------------------------------------------------------------------
; ----------------------------------------------------------------------------------------------------
SolveBoardAt_X1_Y3:
; ----------------------------------------------------------------------------------------------------
   if Board_X1_Y3

      ; Hori Strip ------------------------------------
       if ((Board_X1_Y3=Key)+(Board_X2_Y3=Key)+(Board_X3_Y3=Key))=3  then result=1:goto done

      ; diag up Strip ------------------------------------
       if ((Board_X1_Y3=Key)+(Board_X2_Y2=Key)+(Board_X3_Y1=Key))=3  then result=1:goto done

   endif


; ----------------------------------------------------------------------------------------------------
SolveBoardAt_X2_Y3:
; ----------------------------------------------------------------------------------------------------
; ----------------------------------------------------------------------------------------------------
SolveBoardAt_X3_Y3:
; ----------------------------------------------------------------------------------------------------
Done:
EndPsub Result